(2)优先级队列
<1>以最小二叉堆为例:
我们知道二叉堆的根节点最小值,正好符合了最小优先级队列每次取出最小值的特征,又我们知道优先级队列通常是里面的key值会有所变化,或者会加入新的节点而二叉堆o(lgn)的重新调整为最小二叉堆的能力,使得二叉堆完美的实现了优先级队列的需求。
<2>实现描述
优先级队列通常有如下操作:
HeapMinimum :返回队列中的最小值
HeapExtractMin :返回队列中最小值并且去掉该最小值
HeapDecreaseKey :对某个节点值进行key值的变化
MinHeapInsert :插入一个新节点
MinHeapify :不可或缺的堆调整
优先级队列源码:
#include
usingnamespace std;
#defineINFINITY 0xfffffff
//i节点的父节点的下标
inlineint Parent(int i)
{
return (i-1)/2;
}
//i节点的左孩子的下标
inlineint Left(int i)
{
return 2*i+1;
}
//i节点的右孩子的下标
inlineint Right(int i)
{
return 2*i+2;
}
//swapa[i] and a[j]
inlinevoid Swap(int a[],int i,int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
//another solution
//a[i]^=a[j];a[j]^=a[i];a[i]^=a[j];
}
//Makethe subtree with the root a[i] be the Min Heap
voidMinHeapify(int a[],int heap_size,int i)
{
int left=Left(i);
int right=Right(i);
int min=i;
if(left
if(right
if(min!=i)
{
Swap(a,i,min);
MinHeapify(a,heap_size,min);
}
}
//returnthe min of the heap
intHeapMinimum(int a[])
{
return a[0];
}
//Extractthe min and return the min
intHeapExtractMin(int a[],int& heap_size)
{
if(heap_size<1)
return -1;
int min=a[0];
a[0]=a[heap_size-1];
heap_size-=1;
MinHeapify(a,heap_size,0);
return min;
}
//Decreasethe key value of a[i]
voidHeapDecreaseKey(int a[],int i,int key)
{
if(key>=a[i])
return;
a[i]=key;
while(i>0&&a[Parent(i)]>a[i])
{
Swap(a,i,Parent(i));
i=Parent(i);
}
}
voidMinHeapInsert(int a[],int& heap_size,int key)
{
heap_size+=1;
a[heap_size-1]=INFINITY;
HeapDecreaseKey(a,heap_size-1,key);
}
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。