// pqueue.h: interface for the pqueue class.
//
//////////////////////////////////////////////////////////////////////

#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 // _MSC_VER > 1000

#include<vector>
#include<iostream>
using namespace std;

template <class Object>
class pqueue  
{
public:
	pqueue() : size(0) {
		Object dummy;
		array.push_back(dummy); //element at 0 is dummy
	};
	
	virtual ~pqueue(){};

	void push(Object e) {
//		cout << "Push ";
		Object e2;
		array.push_back(e2); //make hole
		size++;

		//percolate up
		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() {
//		cout << "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 // !defined(AFX_PQUEUE_H__9E985726_9797_11D3_9349_0060674E1056__INCLUDED_)