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

　　更多：2011年軟考程序員考試復習筆試知識點整理匯總

　　18、二叉堆及其應用

　　(1)堆排序

　　<1> 二叉堆：二叉堆實際上一個完全二叉樹。

　　在最大堆中，父節(jié)點的值大于等于子節(jié)點的值，所以堆的最大值在根部;

　　在最小堆中，父節(jié)點的值小于等于子節(jié)點的值，所以堆的最小值在根部;

　　上圖是一個最小堆

　　<2>二叉堆可用于排序——復雜度為O(nlgn)

　　基本步驟有:

　　a. 建立二叉最大堆;

　　b. 由于最大值在根部，所以每次取出根部值和最后一個節(jié)點交換，堆的size減1，然后重新調(diào)整堆為最大堆，調(diào)整堆的復雜度為o(lgn)。

　　如何建立一個二叉最大堆呢?

　　根據(jù)完全二叉樹的特點，可以知道有孩子的節(jié)點的節(jié)點下標是[0, n/2-1],因此我們從n/2-1開始向上調(diào)整，使之符合父節(jié)點大于孩子節(jié)點這個最大堆的特點。

　　只要建好最大堆，接下來就是步驟2了，注意調(diào)整堆要從根節(jié)點開始調(diào)整，堆的大小要減一。注意：我們的下標從0開始的

　　堆排序源碼：

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

　　inlineint Parent(int i)

　　{

　　return (i-1)/2;

　　}

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

　　inlineint Left(int i)

　　{

　　return 2*i+1;

　　}

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

　　inlineint Right(int i)

　　{

　　return 2*i+2;

　　}

　　voidMaxHeapify(int a[],int heap_size,int i)

　　{

　　int left=Left(i);

　　int right=Right(i);

　　int largest=i;

　　if(lefta[largest])

　　largest=left;

　　if(righta[largest])

　　largest=right;

　　if(largest!=i)

　　{

　　swap(a,i,largest);

　　MaxHeapify(a,heap_size,largest);

　　}

　　}

　　voidBuildMaxHeap(int a[],int n)

　　{

　　int i;

　　for(i=n/2-1;i>=0;i--)

　　MaxHeapify(a,n,i);

　　}

　　voidHeapSort(int a[],int n)

　　{

　　int i;

　　BuildMaxHeap(a,n);

　　for(i=n-1;i>0;i--)

　　{

　　swap(a,i,0);

　　MaxHeapify(a,i,0);

　　}

　　}

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

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

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