优先队列的实现(基于堆)

#include<stdio.h>
struct PriorityQueue
{
	int data[10000];
	int length = 0;

	//保持以index为结点的堆的最大性质 
	int heaplfy(int index)
	{
		int least = index;
		
		if(index * 2 <= length && data[index * 2] > data[least])
		{
			least = index * 2;
		}
		
		if(index * 2 + 1 <= length && data[index * 2 + 1] > data[least])
		{
			least = index * 2 + 1;
		}
		
		if(least != index)
		{
			int temp = data[index];
			data[index] = data[least];
			data[least] = temp;
			heaplfy(least);
		}
		
	}
		/*
		循环不变式:
		a[i]的儿子要a[i]小  
		初始：i = i / 2,改变的只是a[i]的值，所以a[i]的儿子依然维持最大堆的性质
		保持：在每次迭代前,a[i]的儿子 一定要比a[i]的"孙子"大；
		终止：当a[i] > a[i /2]是终止，显然a[i]的父亲要比a[i]大；                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
	
	*/ 
	int IncreaseKey(int i,int k)
	{
		if(data[i] < k)
		{
			data[i] = k;
			while(i > 1 && data[i / 2] < data[i])
			{
				int temp = data[i / 2];
				data[i / 2] = data[i];
				data[i] = temp;
				i = i / 2;
			}
		}
	}
	//将a插入堆中 
	void insert(int a)
	{
		if(length == 0)
		{
			length++;
			data[length] = a;
		}
		else
		{
			length++;
			data[length] = -0x3f3f3f;
			IncreaseKey(length,a);
		}
	}
	
	//返回队列首元素 
	int MaxImum()
	{
		return data[1];
	}
	// 返回队列首元素 并把它从堆中去掉 
	int ExtractMax()
	{
		int max1 = data[1];
		data[1] = data[length];
		length--;
		heaplfy(1);
		return max1;
		
	}

	
};

/*
10
10 8 16 7 9 3 1 4 14 2
*/
int main()
{
	PriorityQueue a;
	int n;
	scanf("%d",&n);
	for(int i = 1; i <=n;i++)
	{
		int key;
		scanf("%d",&key);
		a.insert(key);
	
		 
	}
	for(int i = 1; i <= a.length;i++)
	printf("%d ",a.data[i]);
	printf("\n");
	
	//利用ExtractMax进行从大到小排序 
	for(int i = 1; i <= 10; i++)
	{
		int min1 = a.ExtractMax();
		printf("%d ",min1);
	}
	
	printf("\n");
	
	
	return 0;
}