#if !defined(AFX_PQUEUE_H__9E985726_9797_11D3_9349_0060674E1056__INCLUDED_)
#define AFX_PQUEUE_H__9E985726_9797_11D3_9349_0060674E1056__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif
#include<vector>
#include<iostream>
using namespace std;
template <class Object>
class pqueue
{
public:
pqueue() : size(0) {
Object dummy;
array.push_back(dummy); };
virtual ~pqueue(){};
void push(Object e) {
Object e2;
array.push_back(e2); size++;
int hole = size;
for ( ; e < array[hole/2] && (hole > 1) ; hole /= 2)
array[hole] = array[hole/2];
array[hole] = e;
};
Object top() {
return array[1];
};
void pop() {
array[1] = array[size--];
if (size <= 0) {
size = 0;
return;
}
percolateDown(1);
}
void percolateDown(int hole){
int child;
Object tmp = array[hole];
for (; hole* 2 < size; hole= child){
child = hole * 2;
if (child != size && array[child+1] < array[child])
child++;
if (array[child] < tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
};
bool empty(){
if (size == 0)
return true;
return false;
};
void sort(){
while (!empty()){
Object e = pop();
array[size+1] = e;
}
}
private:
vector<Object> array;
int size;
};
#endif