深入理解堆排序的过程
编写代码在程序开发中是值得大家学习的，而编写代码的时候有正确的输入输出，本文是爱站技术频道小编带给大家的深入理解堆排序的过程，在这里可以保证一切服务都可以让你满意。
堆排序过程
堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
既然是堆排序，自然需要先建立一个堆，而建堆的核心内容是调整堆，使二叉树满足堆的定义（每个节点的值都不大于其父节点的值）。调堆的过程应该从最后一个非叶子节点开始，假设有数组A = {1, 3, 4, 5, 7, 2, 6, 8, 0}。那么调堆的过程如下图，数组下标从0开始，A[3] = 5开始。分别与左孩子和右孩子比较大小，如果A[3]最大，则不用调整，否则和孩子中的值最大的一个交换位置，在图1中是A[7] > A[3] > A[8]，所以A[3]与A[7]对换，从图1.1转到图1.2。
所以建堆的过程就是
for ( i = headLen/2; i >= 0; i++)
do AdjustHeap(A, heapLen, i)
建堆完成之后，堆如图1.7是个大根堆。将A[0] = 8 与 A[heapLen-1]交换,然后heapLen减一，如图2.1，然后AdjustHeap(A, heapLen-1, 0)，如图2.2。如此交换堆的第一个元
素和堆的最后一个元素，然后堆的大小heapLen减一，对堆的大小为heapLen的堆进行调堆，如此循环，直到heapLen == 1时停止，最后得出结果如图3。
/*
输入：数组A，堆的长度hLen，以及需要调整的节点i
功能：调堆
*/
void AdjustHeap(int A[], int hLen, int i)
{
int left = LeftChild(i); //节点i的左孩子
int right = RightChild(i); //节点i的右孩子节点
int largest = i;
int temp;
while(left {
if (left {
largest = left;
}
if (right {
largest = right;
}
if (i != largest) //如果最大值不是父节点
{
temp = A[largest]; //交换父节点和和拥有最大值的子节点交换
A[largest] = A[i];
A[i] = temp;
i = largest; //新的父节点，以备迭代调堆
left = LeftChild(i); //新的子节点
right = RightChild(i);
}
else
{
break;
}
}
}
/*
输入：数组A，堆的大小hLen
功能：建堆
*/
void BuildHeap(int A[], int hLen)
{
int i;
int begin = hLen/2 - 1; //最后一个非叶子节点
for (i = begin; i >= 0; i--)
{
AdjustHeap(A, hLen, i);
}
}
/*
输入：数组A，待排序数组的大小aLen
功能：堆排序
*/
void HeapSort(int A[], int aLen)
{
int hLen = aLen;
int temp;
BuildHeap(A, hLen); //建堆
while (hLen > 1)
{
temp = A[hLen-1]; //交换堆的第一个元素和堆的最后一个元素
A[hLen-1] = A[0];
A[0] = temp;
hLen--; //堆的大小减一
AdjustHeap(A, hLen, 0); //调堆
}
}
性能分析
•调堆：上面已经分析了，调堆的运行时间为O(h)。
•建堆：每一层最多的节点个数为n1 = ceil(n/(2^(h+1))),
因此，建堆的运行时间是O(n)。
•循环调堆（代码67-74），因为需要调堆的是堆顶元素，所以运行时间是O(h) = O(floor(logn))。所以循环调堆的运行时间为O(nlogn)。
总运行时间T(n) = O(nlogn) + O(n) = O(nlogn)。对于堆排序的最好情况与最坏情况的运行时间，因为最坏与最好的输入都只是影响建堆的运行时间O(1)或者O(n)，而在总体时间中占重要比例的是循环调堆的过程，即O(nlogn) + O(1) =O(nlogn) + O(n) = O(nlogn)。因此最好或者最坏情况下，堆排序的运行时间都是O(nlogn)。而且堆排序还是原地算法（in-place algorithm）。
如果大家对深入理解堆排序的过程还是不理解，建议大家打开js.aizhan.com，这里可以让你找到一切你想要知道的答案。
上一篇：单链表的快速排序
下一篇：深入了解C++中的关键词
