maxheap.h

大顶堆实现一个优先队列。对于队列的操作应该至少支持下列几种指令： Void enqueue[int ObjectID, int Priority] Int dequeue[]

#include "Object.h"
#include <iostream>
using namespace std;
class Maxheap {
private:
	Object *heap;								//point to the heap array
	int map[1000];								//the help array
	int n;										//the total number of the current Object
	int size;									//the total number of the heap Object
	void siftdown(int);							//help build the heap array
public:
	Maxheap (Object *h,int num,int max)
	{heap = h; n = num; size = max; }
	void buildHeap()
	{	for(int i = n/2-1;i>=0;i--)  siftdown(i);
		for(int j = n-1;j>=0;j--) helpMap(j);
	}
	bool isLeaf(int pos)						//is leaf or not
	{return (pos >=n/2)&&(pos<n);}
	int leftChild(int pos)						//return pos of leftchild
	{return 2*pos+1;}
	int rightChild(int pos)						//return pos of rightchild
	{return 2*pos+2;}
	int parent(int pos)							//return pos of parents
	{return (pos-1)/2;}
	void swap(int i,int j)						//swap two objects
	{Object temp ;temp = heap[i];heap[i]=heap[j];heap[j]=temp;}
	void print()
	{int i;for(i=0;i<n;i++) cout << "("<<heap[i].ID<<","<<heap[i].priority<<")" <<" ";}
	bool enqueue(Object o);						//add a object
	int dequeue();								//delete a object
	void changeWeight(Object o);				//change object's priority
	void helpMap(int i)							//help build map array				
	{	int j ;	j= heap[i].ID;	map[j] = i;	}
	void printMap() 
	{int i;for(i=0;i<100;i++) cout << map[i]<<" ";cout <<endl;}
	void nullMap(int i)							//set deleted object to -1
	{map[i] = -1;}
};