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