2011年软考程序员考试复习笔试知识点整理(14)2

 　(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

　　min=left;

　　if(right

　　min=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);

　　}