구현 - 우선순위 큐와 힙
흠.. 뭔가 찝찝한데 뭘까
#pragma once
#include <iostream>
#include <iomanip>
using namespace std;
#define MAX_SIZE 200
class MaxHeap
{
public:
MaxHeap() { };
// [1 : size]
bool isEmpty() { return _back == 0; }
bool isFull() { return _back == MAX_SIZE - 1; }
void push(int n)
{
if (isFull()) return;
++_back;
size_t i = _back;
for ( ; i != 1 && n > _data[i / 2]; i /= 2)
{
_data[i] = _data[i / 2];
}
_data[i] = n;
}
void pop()
{
if (isEmpty())throw;
int backVal = _data[_back--];
int i = 1;
while (i * 2 <= _back)
{
int bigChildIndex = i * 2;
if(i * 2 + 1 <= _back)
bigChildIndex = _data[i * 2] > _data[i * 2 + 1] ? i * 2 : i * 2 + 1;
if (backVal < _data[bigChildIndex])
{
_data[i] = _data[bigChildIndex];
i = bigChildIndex;
}
else
break;
}
_data[i] = backVal;
}
int front(int n)
{
if (isEmpty()) throw;
return _data[1];
}
void display()
{
if (isEmpty()) cout << "is empty\n";
for (int i = 1, level = 1; i <= _back; i++)
{
if (i == level)
{
cout << endl;
level *= 2;
}
cout << setw(5) << '(' << i << ')' << _data[i];
}
}
private:
int _data[MAX_SIZE];
int _back{0};
};
#include "priority_queue.h"
#include <ctime>
void main()
{
MaxHeap mh;
srand(size_t(time(NULL)));
for(size_t i = 0; i < 7; ++i)
mh.push(rand() % 100);
while (!mh.isEmpty())
{
mh.pop();
mh.display();
cout << endl;
}
}
