前段时间在看侯捷的STL源码剖析,看到堆这一章顺带复习了一下堆排序,我们所说的堆一般指的是二叉堆,下面先来看下二叉堆的定义。
二叉堆定义
二叉堆是完全二叉树或是近似完全二叉树。
二叉堆满足两个特性:
1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。
最大堆:父结点的键值总是大于或等于任何一个子节点的键值;最小堆:父结点的键值总是小于或等于任何一个子节点的键值。
存储
二叉堆一般用数组来表示。例如,根节点在数组中的位置是0,第n个位置节点的子节点位置在2n+1、2n+2。这种方式便于查找节点的子节点及父节点。如,位置0的子节点在1、2,位置1的子节点在3、4。
二叉堆插入
插入操作一般把数据插入到数组的最后面,然后,由此节点向上调整二叉堆,以满足二叉堆的性质。代码如下:
void push_heap(int array[], int hopeInd, int topInd, int value){ int parent = (hopeInd - 1) / 2; while (hopeInd > topInd && array[parent] < value){ array[hopeInd] = array[parent]; hopeInd = parent; parent = (hopeInd - 1) / 2; } array[hopeInd] = value; }
二叉堆删除
二叉堆的删除操作与插入相反,插入是“向上冒”,而删除时“向下沉”,即把根节点移除并把最后一个节点移到最前面,然后由此节点往下调整二叉堆。代码如下:
void fix_down_heap(int array[], int hopeInd, int size, int value){ int secondChild = hopeInd * 2 + 2; int topInd = hopeInd; while (secondChild < size){ if (array[secondChild-1] > array[secondChild]){ secondChild--; } array[hopeInd] = array[secondChild]; hopeInd = secondChild; secondChild = hopeInd * 2 + 2; } if (secondChild == size){ array[hopeInd] = array[secondChild-1]; hopeInd = secondChild - 1; } push_heap(array, hopeInd, topInd, value); }
数组堆化
在进行二叉树排序之前,需要把数组转化为二叉堆,即数组堆化。由最后一个非子节点开始至根节点,一个个向下进行堆调整,即可完成堆的建立。建立堆的代码如下:
void make_heap(int array[], int size){ int hopeInd = (size - 2) / 2; while (hopeInd >= 0){ fix_down_heap(array, hopeInd, size, array[hopeInd]); hopeInd--; } }
排序实现
对数组建立堆之后就可以进行排序操作了。根据二叉堆的性质,根节点是所有节点中值最大或最小的,因此堆排序就是一个不断删除根节点然后调整堆直到只有一个元素的过程。代码如下:
void swap(int& a, int& b){ if (a != b){ a ^= b; b ^= a; a ^= b; } }
void heapSort(int array[], int length){ make_heap(array, length); for (int i=length-1; i>0; i--){ swap(array[i], array[0]); fix_down_heap(array, 0, i, array[0]); } }
至此,堆排序结束。
刚开始学习写博客,如有不足之处,欢迎指出。谢谢!
相关推荐
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
堆排序的c++实现代码
C语言堆排序实现优先序列,将十个实验数据先建大顶堆,再按优先队列输出。
堆排序呢认识文档。、,其中对于堆排序做了一些介绍和一些例子
完整详细版Python全套教学课件 第05节 堆排序实现.pdf
这是一个用C++编写的简单学生成绩管理系统,其中实现学生成绩的最大最小堆排序,程序已经过测试!
找出一个序列中前M个大值对应的索引(堆排序实现),比如有一个数组a[50],要找出数组a中前十个最大值的索引号,并把索引号记录到b[10]中。
1、 实现堆排序算法。 2、 理论分析并实验验证堆排序算法的时间复杂度。
用Java实现的堆排序算法,二叉树转换为堆,然后排序
自己做的 很辛苦的。堆排序课设的代码,用c语言做的 数据结构堆排序的算法演示~~~可以借鉴或 参考
本文实例讲述了C#堆排序实现方法。分享给大家供大家参考。具体如下: private static void Adjust (int[] list, int i, int m) { int Temp = list[i]; int j = i * 2 + 1; while (j <= m) { //more ...
找工作期间整理的各种排序方式。有相关的Java代码和时间复杂度空间复杂度分析。
用c语言实现堆排序算法,堆排序算法的实现,分析堆排序算法
堆排序5.cpp 使用C++实现的堆排序堆排序5.cpp 使用C++实现的堆排序堆排序5.cpp 使用C++实现的堆排序堆排序5.cpp 使用C++实现的堆排序堆排序5.cpp 使用C++实现的堆排序堆排序5.cpp 使用C++实现的堆排序堆排序5.cpp ...
堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆...
Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C
数据结构中,利用C++实现最小堆排序,内含类
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
C语言实现的堆排序算法。 提供了堆排序算法的一个接口,可以为其它功能提供功能。