2011年軟考程序員考試復(fù)習(xí)筆試知識點整理(14)

　　(2)優(yōu)先級隊列

　　<1>以最小二叉堆為例：

　　我們知道二叉堆的根節(jié)點最小值，正好符合了最小優(yōu)先級隊列每次取出最小值的特征，又我們知道優(yōu)先級隊列通常是里面的key值會有所變化，或者會加入新的節(jié)點而二叉堆o(lgn)的重新調(diào)整為最小二叉堆的能力，使得二叉堆完美的實現(xiàn)了優(yōu)先級隊列的需求。

　　<2>實現(xiàn)描述

　　優(yōu)先級隊列通常有如下操作：

　　HeapMinimum :返回隊列中的最小值

　　HeapExtractMin ：返回隊列中最小值并且去掉該最小值

　　HeapDecreaseKey ：對某個節(jié)點值進(jìn)行key值的變化

　　MinHeapInsert ：插入一個新節(jié)點

　　MinHeapify :不可或缺的堆調(diào)整

　　優(yōu)先級隊列源碼：

　　#include

　　usingnamespace std;

　　#defineINFINITY 0xfffffff

　　//i節(jié)點的父節(jié)點的下標(biāo)

　　inlineint Parent(int i)

　　{

　　return (i-1)/2;

　　}

　　//i節(jié)點的左孩子的下標(biāo)

　　inlineint Left(int i)

　　{

　　return 2*i+1;

　　}

　　//i節(jié)點的右孩子的下標(biāo)

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

　　}

　　軟考程序員考試歷年真題重點題總結(jié)及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)