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

 　18、二叉堆及其应用

　　(1)堆排序

　　< 1> 二叉堆：二叉堆实际上一个完全二叉树。

　　在最大堆中，父节点的值大于等于子节点的值，所以堆的最大值在根部;

　　在最小堆中，父节点的值小于等于子节点的值，所以堆的最小值在根部;

　　上图是一个最小堆

　　< 2>二叉堆可用于排序--复杂度为O(nlgn)

　　基本步骤有:

　　a. 建立二叉最大堆;

　　b. 由于最大值在根部，所以每次取出根部值和最后一个节点交换，堆的size减1，然后重新调整堆为最大堆，调整堆的复杂度为o(lgn)。

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

　　根据完全二叉树的特点，可以知道有孩子的节点的节点下标是[0, n/2-1],因此我们从n/2-1开始向上调整，使之符合父节点大于孩子节点这个最大堆的特点。

　　只要建好最大堆，接下来就是步骤2了，注意调整堆要从根节点开始调整，堆的大小要减一。注意：我们的下标从0开始的

　　堆排序源码：

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

　　}

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

　　{

　　int left=Left(i);

　　int right=Right(i);

　　int largest=i;

　　if(left

　　largest=left;

　　if(right

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

　　}

　　}