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

　　更多：2011年軟考程序員考試復(fù)習(xí)筆試知識點(diǎn)整理匯總

　　18、二叉堆及其應(yīng)用

　　(1)堆排序

　　<1> 二叉堆：二叉堆實(shí)際上一個(gè)完全二叉樹。

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

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

　　上圖是一個(gè)最小堆

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

　　基本步驟有:

　　a. 建立二叉最大堆;

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

　　如何建立一個(gè)二叉最大堆呢?

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

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

　　堆排序源碼：

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

　　inlineint Parent(int i)

　　{

　　return (i-1)/2;

　　}

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

　　inlineint Left(int i)

　　{

　　return 2*i+1;

　　}

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

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

　　}

　　}

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

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

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