206
排序算法系列之堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
1 堆排序定义
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤
)若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
下图来自《算法导论》中堆排序一节：放到这里帮助大家更形象的理解堆。
图(a)是一个最大堆，图(b)是最大堆的数组表示。
2 堆节点的访问
通常堆是通过一维数组来实现的。在起始数组为 1 的情形中：
- 父节点i的左子节点在位置
- LEFT(i) return (2*i);
- 父节点i的右子节点在位置
- RIGHT(i) return (2*i+1);
- 子节点i的父节点在位置
- PARENT(i) return floor((i/2)）;
3 堆的操作
我们以最大堆排序来说明排序过程。
在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作：
- 最大堆调整（MaxHeapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（BuildMaxHeap）：将堆所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
4 堆排序特点
堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。
5 堆排序
算法动画演示
大根堆排序实例：对于关键字序列(42，13，24，91，23，16，05，88)，在建堆过程中完全二叉树及其存储结构的变化情况。
动画演示：【动画演示】
堆排序c/c++实现
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
堆操作的实现：
（1）最大堆调整MaxHeapify(A,i);
// 使以i为根的子树成为最大堆
void MaxHeapify(int arr[],int len,int i)
{
int l = 2*i,r = 2*i+1;
int largest;
if(l<=len && arr[l]>arr[i])
largest = l;
else
largest = i;
if(r<=len && arr[r]>arr[largest])
largest = r;
if(largest != i)
{
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
MaxHeapify(arr,len,largest);
}
}
（2）创建最大堆BuildMaxHeap(A)
void BuildMaxHeap(int arr[],int len)
{
for(int i=len/2;i>=1;i--)
{
MaxHeapify(arr,len,i);
}
cout<<"build heap is ok!"<<endl;
}（3）堆排序HeapSort(A)void HeapSort(int arr[],int len)
{
BuildMaxHeap(arr,len);
printvalue(arr,len);
for(int i=len;i>=2;i--)
{
int temp = arr[1];
arr[1] = arr[i];
arr[i] = temp;
len--;
MaxHeapify(arr,len,1);
}
}
6 算法分析
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用最大堆调整MaxHeapify(A,i)实现的。堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。
7 堆排序与直接插入排序的区别
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果，可减少比较次数。
8 参考文章
2.堆排序基础讲解：https://www.wutianqi.com/?p=1820；
3.算法导论学习总结：https://www.wutianqi.com/?p=2343；
9 整体代码（包括实验程序C++）
#include <cstdlib>
#include <iostream>
using namespace std;
void printvalue(int arr[],int len)
{
int i;
cout<<"the arr value:";
for(i=1;i<=len;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
void MaxHeapify(int arr[],int len,int i)
{
int l = 2*i,r = 2*i+1;
int largest;
if(l<=len && arr[l]>arr[i])
{
largest = l;
}
else
{
largest = i;
}
if(r<=len && arr[r]>arr[largest])
{
largest = r;
}
if(largest != i)
{
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
MaxHeapify(arr,len,largest);
}
}
void BuildMaxHeap(int arr[],int len)
{
for(int i=len/2;i>=1;i--)
{
MaxHeapify(arr,len,i);
}
cout<<"build heap is ok!"<<endl;
}
void HeapSort(int arr[],int len)
{
BuildMaxHeap(arr,len);
printvalue(arr,len);
for(int i=len;i>=2;i--)
{
int temp = arr[1];
arr[1] = arr[i];
arr[i] = temp;
len--;
MaxHeapify(arr,len,1);
}
}
int main(int argc, char *argv[])
{
int a[100];
int len =88;
for(int i=1;i<=len;i++) //88个数
{
a[i] = len - i + 1;
}
cout<<"init a[]:";
printvalue(a,len);
cout<<endl;
HeapSort(a,len);
cout<<"After HeapSort!"<<endl;
printvalue(a,len);
system("PAUSE");
return EXIT_SUCCESS;
}
最后更新：2017-04-03 18:52:08