구현 - 우선순위 큐와 힙

흠.. 뭔가 찝찝한데 뭘까

#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;

}

}