本文主要是介绍优先队列的实现(基于堆)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#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;
}这篇关于优先队列的实现(基于堆)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
