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

　　}

　　} [NextPage] 

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

　　}

 [NextPage] 　(3)其他应用

　　可使用堆解决下列问题：

　　<>1.构建哈夫曼代码：

　　我们知道在构建哈夫曼树时，每次要选择集合中两个最小的元素，然后将元素值相加，合并为一个新节点，此时两个最小的元素的取出可以用HeapExtractMin函数来实现，产出的新节点需要插入到堆中，我们有MinHeapInsert函数来实现。

　　<>2.计算大型浮点数集合的和：

　　我们知道大浮点数和小浮点数相加，很可能会造成精度误差。所以可以每次从优先级队列中取出最小的两个数相加，和1的实现差不多。

　　<>3.将多个小型有序文件合并到一个大型有序文件中：

　　假设有 n个小型有序文件，建立一个大小为n的最小堆，每个有序文件贡献一个(如果有的话)，每次取出最小值插入到大型文件中，并且去掉该最小元素，并将它在文件中的后续元素插入到堆中,能够在o(lgn)的时间内从n个文件中选择要插入到大型文件中的元素。

　　<>4.在具有10亿个数值的集合中找到100万个最大的数：

　　建立100万个元素的最小二叉堆，后面的数和根部进行比较，如果大于根部，进行堆调整。

　　1.n×m遍扫描

　　【算法基本描述】n×m遍扫描

　　【算法复杂度】O(nm)

　　【算法思想】每次都扫描一遍数组，取出最大元素，这样扫描m遍就能得到m个最大的数。

　　2.排序后取最大m个数

　　【算法基本描述】对n个数排序，对拍完序后的序列取m个最大的数

　　【算法复杂度】视排序的复杂度，一般为O(nlogn)或O(n^2)

　　3.最小堆

　　【算法基本描述】一遍扫描+最小堆

　　【算法复杂度】O(nlogm) 遍历O(n) 最小堆O(logm)

　　【算法伪代码】

　　建立一个最小堆(优先队列)，最小堆的大小控制在m之内;

　　for 每个数：

　　if 这个数比最小堆的堆顶元素大：

　　弹出最小堆的最小元素，

　　*把这个数插入到最小堆;

　　最小堆中的m个元素就是所要求的元素;

　　中最小堆的作用就是保持里面始终有m个最大元素，且m个元素中最小的元素在堆顶。

　　【其他】如果要求n个数中取最小的m个，只要大顶堆即可

　　总结：当n与m差不多大时，采用复杂度较低的排序是比较可取的，因为简单。当m<

　　我不敢说我的算法是最好的，但是它一定是一个复杂度较低的算法。

　　使用用最小堆来找最大的K个数源码