首页 > 代码库 > 【数据结构】优先队列和堆
【数据结构】优先队列和堆
优先队列（priority queue）
对于一般的队列是在队列的尾部添加数据，在头部删除，以便先进先出。
而优先队列中的每个元素都有一个优先级，每次将一个元素放入队列中，而每次出队时都是将优先级最大的那个元素出队，称为高进先出（largest-in，first-out）。
优先队列必须实现以下几个操作
1.入队（push）：将一个元素放入队列中。
2.出队（pop）:将优先级最高的元素从队列中删除。
要实现上面的操作可以维护一个有序的链表。每次插入数据时维护整个链表有序，即使用插入法，每次出队的操作只需要删除链表最前面的元素。
这么做的话入队操作的复杂度是O（n），出队是O（1），综合复杂度为O（n）。
接下来要介绍的是O（logn） 的数据结构——二叉堆。
给定一棵完全二叉树，该树的每个节点的优先级大于该节点的所有孩子节点的优先级。易知，根节点将是优先级最高的节点。
要用二叉堆来实现优先队列，必须完成的两个操作：
1.入队（push）：对于一棵空的二叉堆，只需要将入堆的元素加入根节点即可。对于一般情况，我们将该元素直接加入完全二叉树的一个位置，该位置是指将这个位置加入该完全二叉树，这个树仍然是完全二叉树的那个点。之后将这个元素和他的父节点比较，若优先级大于该父节点，则与父节点交换位置，再将新插入的这个元素再和它的新父节点比较，直到它没有父节点或有一个父节点优先级大于它为止。
2.出队（pop）：要拿出该完全二叉树的根节点，之后要维护剩下的节点满足二叉堆的性质。
在讲这个操作之前，我们先定义一个新的操作——假设某节点的左右两棵子树都满足堆的性质，要将整个树也变成一个堆。我们把该操作称为筛选（sift）。对于筛选算法我们需要将根节点和两个子节点比较，若根节点的优先级最大，则已经调整完成，否则将两个子节点中较大的那个和根节点进行交换，此时根节点将是最大的元素了，然后跟踪被交换的那个孩子节点的位置，继续做如上的调整，直到调整结束。
对于出队操作，删除根节点的元素，并将该二叉堆的最后一个元素（所谓最后一个元素是指将该元素从完全二叉树删除，该二叉树仍然是完全二叉树的那个元素）放到根节点的位置，然后对该树进行筛选操作。
一般的来讲，堆可以轻易地用数组实现，假设数组编号为1的元素是根节点，那么2和3分别是它的左右节点。对于一个数组编号为i（i>=1）的节点，他的左右节点分别为i*2和i*2+1。
要将一个数组中的n个元素（编号从1到n）直接变成堆，可以用以下操作：for(i=n/2;i>=1;i--) sift(以编号为i的节点为根节点)。这是因为超过n/2的那些节点都是叶子节点，满足堆的性质，其他节点从下往上依次进行sift操作就完成的堆的建立。
1 #include<stdio.h> 2 /*r[0].fix为堆的长度*/ 3 typedef int elemtype; 4 typedef struct node 5 { 6 elemtype data; 7 int fix; 8 }HeapNode; 9 HeapNode out(HeapNode r[],int s)/*r[s]出堆*/10 {11 int i,j;12 HeapNode item;13 item=r[s];/*数据暂存*/14 r[s]=r[r[0].fix];/*最后一个数据放入要出堆的元素的位置上*/15 r[0].fix--;/*长度减一*/16 sift(r,s,r[0]);17 return item;18 }19 void in(HeapNode r[],HeapNode item)/*入堆*/20 {21 int i;22 for(i=r[0].fix+1;i>1;i/=2)23 {24 if(item.fix</*>*/r[i/2].fix) r[i]=r[i/2];25 else break;26 }27 r[i]=item;28 r[0].fix++;29 }30 void sift(HeapNode r[],int s,int t)/*筛选成小顶堆算法*/31 {/*r[s...t]中的记录除r[s]外均满足堆的特性*/32 int i,j;33 HeapNode item;34 item=r[s];35 i=s;36 j=2*i;37 while(j<=r[0].fix)38 {39 if(j+1<=r[0].fix&&r[j+1].fix</*>*/r[j].fix) j++;40 if(item.fix>/*<*/r[j].fix){r[i]=r[j];i=j;j=2*i;}41 else break;42 }43 r[i]=item;44 }45 /*46 初始堆的建立：47 for(i=n/2;i>=1;--) sift(r,i,n);48 */49 /*堆排序*/50 /*大顶堆完成升序，小顶堆完成降序*/51 void Heat_sort(long r[],int n)52 {53 int i;54 long item;55 for(i=n/2;i>=1;i--) sift(r,i,n);/*初始堆的建立*/56 for(i=n;i>=2;i--)57 {58 item=r[i];59 r[i]=r[1];60 r[1]=item;61 sift(r,1,i-1); /*大顶堆完成升序，小顶堆完成降序*/62 }63 }