# 堆排序的Python实现
# coding:utf-8 import random import time t = time.time() # 堆排序, 按照从小到大排序，所以建立大根堆 # 列表的第一个元素没有使用 def ShiftDown(a, i): if not a: return j = i N = len(a) while 2*j < N: # 存在左孩子时 ci = 2 * j # 左孩子节点下标 if ci + 1 < N and a[ci] < a[ci + 1]: # ci保存左右孩子节点中大值的下标 ci += 1 if a[j] < a[ci]: # 和孩子互换，否则，该元素位置正确，可以退出 a[j], a[ci] = a[ci], a[j] else: break j = ci def BuildHeap(a): if not a: return i = len(a)/2 while i >= 1: #print a[i] ShiftDown(a, i) i -= 1 def HeapSort(a): BuildHeap(a) b = [] while len(a) > 1: # 列表的第一个元素没有使用 a[1], a[-1] = a[-1], a[1] # 将最大元素和最后一个元素互换，弹出最大元素，重新建造堆 b.append(a.pop()) BuildHeap(a) a = b[::-1] b.sort() print a == b #print b[::-1] #a[N - 1], a[0] = a[0], a[N - 1] a = [random.randint(1,100) for i in range(1001)] #a = [60, 39, 80, 25, 66, 3, 93, 92, 11, 11, 38] print a BuildHeap(a) print a HeapSort(a) print time.time() - t
以下是C语言实现：
1 // 最大堆实现, 数组下标从1开始，a[0]不使用。 2 3 // 交换两数 4 void swap(int &a, int &b) { 5 int t = a; 6 a = b; 7 b = t; 8 } 9 10 // 把第i个元素向上移动 11 void ShiftUp(int a[], int i) { 12 while(i>1 && a[i]>a[i/2]) { 13 swap(a[i], a[i/2]); 14 i >>= 1; 15 } 16 } 17 18 // 把第i个元素向下移动 19 void ShiftDown(int a[], int n, int i) { 20 while((i=2*i) <= n) { 21 if(i+1<=n && a[i+1]>a[i]) ++i; 22 if(a[i] > a[i/2]) swap(a[i], a[i/2]); 23 else break; 24 } 25 } 26 27 // 把数组a变成具备最大堆性质的数组 28 void MakeHeap(int a[], int n) { 29 for(int i=n/2; i>0; --i) 30 ShiftDown(a, n, i); 31 } 32 33 // 向堆中插入元素x 34 void Insert(int a[], int &n, int x) { 35 a[++n] = x; 36 ShiftUp(a, n); 37 } 38 39 // 删除堆中第i个元素 40 void Del(int a[], int &n, int i) { 41 a[i] = a[n--]; 42 if(i>1 && a[i]>a[i/2]) ShiftUp(a, i); 43 else ShiftDown(a, n, i); 44 } 45 46 // 堆排序，时间复杂度O(nlogn) 47 void HeapSort(int a[], int n) { 48 MakeHeap(a, n); 49 for(int i=n; i>1; --i) { 50 swap(a[i], a[1]); 51 ShiftDown(a, i-1, 1); 52 } 53 }
还有另外一个版本：
1 //删除最大的元素 2 int deletemax() 3 { 4 int t; 5 t=h[ 1];//用一个临时变量记录堆顶点的值 6 h[ 1]=h[ n];//将堆得最后一个点赋值到堆顶 7 n--;//堆的元素减少1 8 siftdown(1);//向下调整 9 return t;//返回之前记录的堆得顶点的最大值 10 } 11 12 13 #include <stdio.h> 14 int h[ 101];//用来存放堆的数组 15 int n;//用来存储堆中元素的个数，也就是堆的大小 16 17 //交换函数，用来交换堆中的两个元素的值 18 void swap(int x,int y) 19 { 20 int t; 21 t=h[ x]; 22 h[ x]=h[ y]; 23 h[ y]=t; 24 } 25 26 //向下调整函数 27 void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整 28 { 29 int t,flag=0;//flag用来标记是否需要继续向下调整 30 //当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行 31 while( i*2<=n && flag==0 ) 32 { 33 //首先判断他和他左儿子的关系，并用t记录值较小的结点编号 34 if( h[ i] > h[ i*2] ) 35 t=i*2; 36 else 37 t=i; 38 //如果他有右儿子的情况下，再对右儿子进行讨论 39 if(i*2+1 <= n) 40 { 41 //如果右儿子的值更小，更新较小的结点编号 42 if(h[ t] > h[ i*2+1]) 43 t=i*2+1; 44 } 45 //如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的 46 if(t!=i) 47 { 48 swap(t,i);//交换它们，注意swap函数需要自己来写 49 i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整 50 } 51 else 52 flag=1;//则否说明当前的父结点已经比两个子结点都要小了，不需要在进行调整了 53 } 54 } 55 56 //建立堆的函数 57 void creat() 58 { 59 int i; 60 //从最后一个非叶结点到第1个结点依次进行向上调整 61 for(i=n/2;i>=1;i--) 62 { 63 siftdown(i); 64 } 65 } 66 67 //删除最大的元素 68 int deletemax() 69 { 70 int t; 71 t=h[ 1];//用一个临时变量记录堆顶点的值 72 h[ 1]=h[ n];//将堆得最后一个点赋值到堆顶 73 n--;//堆的元素减少1 74 siftdown(1);//向下调整 75 return t;//返回之前记录的堆得顶点的最大值 76 } 77 78 int main() 79 { 80 int i,num; 81 //读入数的个数 82 scanf("%d",&num); 83 84 for(i=1;i<=num;i++) 85 scanf("%d",&h[ i]); 86 n=num; 87 88 //建堆 89 creat(); 90 91 92 //删除顶部元素，连续删除n次，其实夜就是从大到小把数输出来 93 for(i=1;i<=num;i++) 94 printf("%d ",deletemax()); 95 96 getchar(); 97 getchar(); 98 return 0; 99 }
参考文献：
http://www.kancloud.cn/digest/make-thiner-programming-pearls/56357
http://ahalei.blog.51cto.com/4767671/1427156