maxheap.cpp

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

#include "Maxheap.h"

void  Maxheap::siftdown(int pos) {
	while(!isLeaf(pos)) {
		int j = leftChild(pos);int rc = rightChild(pos);
		if((rc<n)&&(heap[j].priority<heap[rc].priority))
			j = rc;
		if(heap[pos].priority>=heap[j].priority) break ;
		else {swap(pos,j); pos = j; }	
	}	
}

bool Maxheap::enqueue(Object o) {
	if (n>=size) return false;
	int curr = n++;
	heap[curr] = o;
	while((curr!=0)&&heap[curr].priority>heap[parent(curr)].priority) {
		swap(curr,parent(curr)); 
		helpMap(curr);
		curr = parent(curr);
	}
	helpMap(curr);
	return true;
}

int Maxheap::dequeue() {
	if(n==0) return -1;
	swap(0,--n);
	int	pos=0;
	if(n!=0)
		while(!isLeaf(pos)) {
		int j = leftChild(pos);int rc = rightChild(pos);
		if((rc<n)&&(heap[j].priority<heap[rc].priority))
			j = rc;
		if(heap[pos].priority>=heap[j].priority) break;
			else {swap(pos,j); helpMap(pos);pos = j; }	
		}
	helpMap(pos);
	nullMap(heap[n].ID);
	return heap[n].ID;
}

void Maxheap::changeWeight(Object o) {
	int pos = map[o.ID];
//	 down
	heap[pos].priority=o.priority;
	while(!isLeaf(pos)) {
		int j = leftChild(pos);int rc = rightChild(pos);
		if((rc<n)&&(heap[j].priority<heap[rc].priority))
			j = rc;
		if(heap[pos].priority>=heap[j].priority) break;
			else {swap(pos,j); helpMap(pos);pos = j; }	
		}	
//  up	
		while((pos!=0)&&heap[pos].priority>heap[parent(pos)].priority) {
		swap(pos,parent(pos)); 
		helpMap(pos);
		pos = parent(pos);
	}
	helpMap(pos);
	
}