基于大根堆的最大优先级队列

《算导》中的最大优先级队列伪代码用的是一维数组,元素只有优先级key,而没有本身的含义,这与实际应用不符,遂改为结构体数组。

//注意:二叉堆的根是heap[1];
#include<stdio.h>
#include<stdlib.h>
#define INT_MIN -2147483647
#define HEAP_INIT_SIZE 0
#define LENGTH 100 
typedef struct{
	int value;//元素本身的值
	int key;//优先级
}node;
node heap[LENGTH];
int heapsize=HEAP_INIT_SIZE,length=LENGTH;
void max_heapify(node *heap,int i);
void build_max_heap(node *heap);
int maxisum(node *heap);
int heap_extract_max(node *heap);
bool heap_increase_key(node *heap,int i,int key);
void max_heap_insert(node *heap,int key,int value);
int main()
{
	/*
	int i;
	max_heap_insert(heap,2,2);
	max_heap_insert(heap,200,200);
	max_heap_insert(heap,1000,1000);
	max_heap_insert(heap,50,50);
	heapsize=4;
	build_max_heap(heap);
	for(i=1;i<=heapsize;i++)
		printf("%d ",heap[i].value);
	printf("\n");
	printf("%d\n",maxisum(heap));
	printf("%d\n",heap_extract_max(heap));
	for(i=1;i<=heapsize;i++)
		printf("%d ",heap[i].value);
	printf("\n");
	heap_increase_key(heap,2,400);
	for(i=1;i<=heapsize;i++)
		printf("%d ",heap[i].key);
	printf("\n");
	max_heap_insert(heap,5444987,5444987);
	for(i=1;i<=heapsize;i++)
		printf("%d ",heap[i].key);
	printf("\n");
	system("pause");
	*/
	return 0;
}
void max_heapify(node *heap,int i)//根节点与孩子关系未确定,但子树都是堆
{
	int largest;
	int l=2*i,r=2*i+1;
	if(l<=heapsize&&heap[l].key>heap[i].key)
		largest=l;
	else
		largest=i;
	if(r<=heapsize&&heap[r].key>heap[largest].key)
		largest=r;
	if(largest!=i)
	{
		node t;
		t=heap[i];
		heap[i]=heap[largest];
		heap[largest]=t;
		max_heapify(heap,largest);
	}
	return;
}
void build_max_heap(node *heap)//将无序数组建成二叉堆
{
	//注意:建堆前应在调用者函数内设置好heapsize
	int i;
	for(i=heapsize/2;i>=1;i--)
	{
		max_heapify(heap,i);
	}
	return;
}
int maxisum(node *heap)//返回优先级最高的元素的优先级(即堆根的key域)
{
	return heap[1].key;
}
int heap_extract_max(node *heap)
{
	if(heapsize<1)
	{
		printf("heap underflow\n");
		return -1;
	}
	int max=heap[1].key;
	heap[1]=heap[heapsize];
	heapsize--;
	max_heapify(heap,1);
	return max;
}
bool heap_increase_key(node *heap,int i,int key)//将元素i的优先级提高到key
{
	if(key<heap[i].key)
		return false;
	heap[i].key=key;
	while(i>1 && heap[i/2].key<heap[i].key)//为什么不直接用max_heapify()?注意max_heapify()的使用条件
	{
		node t=heap[i];
		heap[i]=heap[i/2];
		heap[i/2]=t;
		i=i/2;
	}
	return true;
}
void max_heap_insert(node *heap,int key,int value)//插入优先级为key,值为value的元素
{
	heapsize++;
	heap[heapsize].key=INT_MIN;
	heap[heapsize].value=value;
	heap_increase_key(heap,heapsize,key);
	return;
}