堆(数据结构)的定义:
wiki百科中对堆的定义是
既然堆是一棵树,那么其特点也应该是递归的了。继续wikipedia:
1.父节点的键值总是大于等于(或小于等于)任何子节点的键值
2.每个节点的左右子树都是一个二叉堆(具有树的标志性的递归定义)
其中父节点的键值比子节点大的叫做大根堆,反之则是小根堆。
小根堆例子: 大根堆:(同样数据)
1 9
/ \ / \
4 6 7 8
/ \ / \ / \ / \
5 7 8 9 6 5 4 1
可能大家建的堆跟图中的不一样,但是也符合堆的定义,因此可以看到对于同样一组数据,堆的构建不是唯一的,因此堆排序的不稳定的也不难理解了。
堆排序的时间复杂度是O(NlogN),这个后面会介绍到。
因为其他几种堆(二项式堆,斐波那契堆)用的较少,因此通常来讲,我们习惯将堆默认为二叉堆。
堆是用数组来存储的,采取的是树的双亲存储结构(一种顺序存储结构),原因:堆是一颗完全二叉树,用下标即可表达父子关系,而数组具有操作简单,速度更快的优点。
以上图中的小根堆为例:
1 | 4 | 6 | 5 | 7 | 8 | 9 |
i 节点的孩子下标应该是2 * i + 1(左孩子)和 2 * i + 2(右孩子),父节点的下标应该是(i - 1)/ 2【下标从0开始】
堆排序的过程:(堆的基本操作:插入与删除 包含其中,不再单独介绍)
1)建堆(以大根堆为例)(图源来自http://www.java3z.com/cwbwebhome/article/article1/1362.html?id=4745感谢原博主)
该完全二叉树中,叶节点为30,48,93,15,35,显然,叶节点是满足堆的要求的,因此我们应该从第一个非叶节点 72 开始调整。
72比35大,因此不需要做处理,再看53,比左孩子小,将其与左孩子交换;再看18,比两个孩子都小,应该跟大的换,如果跟30换,那么30还要继续跟48换,从而才能保证根最大;
以此类推...直到根节点
2)排序
建堆工作已经完毕,我们将最大的元素放在了根节点,首先我们将根节点与最后一个节点(35)作交换。第一趟排序完成。93到达了最终位置。将剩余部分继续调整为堆即可,现在堆中只有35一个数字不满足堆的定义。其他记录都满足,因此只需要调整35即可。
具体的步骤就是35一直往下沉,直到满足堆的定义。不再赘述。
经过第二趟排序,我们可以得到次大的元素72,再将72与最后一个节点交换,依照以上处理方法继续处理,直到树中只有一个元素位置,排序结束。
算法思想如下:
public void heapSort(int[] a){ //1.build the heap //2.exchange the first node with the last one,heapLength--; //3.split the biggest node(the last node after changed) with left ones, //4.adjust the first node(after changed)to fit in heap defination }
下面来看代码,首先我们知道,图例介绍中,堆排序主要分为两部分:建堆 & 调整;我们可以看到建堆的过程其实也是在调整,刚好符合树的递归定义,因此,我们先介绍如何调整。
static void ajustHeap(int[] heap, int length, int i) { int left = 2 * i + 1;//左孩子 int right = 2 * i + 2;//右孩子 int big = i;//较大的节点下标 int tem; while (left < length || right < length) {//循环直到确定最终位置 if (left < length && heap[left] > heap[big]) { big = left; } if (right < length && heap[right] > heap[big]) { big = right; }//确定较大键值的下标 if (i == big) {//如果该节点满足要求,则跳出循环 break; } else {//否则与较大键值的孩子交换,并递归往下 tem = heap[i]; heap[i] = heap[big]; heap[big] = tem; i = big; left = 2 * i + 1; right = 2 * 2 + 2; } } }
配合上图中建堆过程中的调整理解。
static void buildHeap(int[] heap, int length) { //从第一个非叶结点开始调整 //由于堆是完全二叉树,因此如果堆的总节点个数是偶数,则最后一个叶节点一定是其父节点的左孩子 //如果堆的总结点数是奇数,则非叶节点均包含两个孩子(扯远了) int begin = length % 2 == 0 ? length / 2 : (length - 1) / 2; for(int i = begin; i >= 0;i--){ ajustHeap(heap, length, i);//建堆的过程就是逐个调整的过程 } }
public static void main(String[] args) { int[] heap = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int length = heap.length; buildHeap(heap, length);//建堆 System.out.println(Arrays.toString(heap)); while (length > 1) { int tem = 0; tem = heap[length - 1]; heap[length - 1] = heap[0]; heap[0] = tem;//将收尾交换 length--;//将最大节点从堆中删除 ajustHeap(heap, length, 0);//调整堆,只需调整第一个节点即可 } System.out.println(Arrays.toString(heap)); } }
打印结果是:
[1, 2, 3, 5, 4, 6, 7, 8, 9]
从代码中可以看出,调整每个节点的时间复杂度是树的高度logN,因此简化后的时间复杂度为O(NlogN)
空间复杂度,由于存在交换键值,因此需要一个额外空间,空间复杂度为O(1)。
堆排序适合记录数很多的情况,比如从100000个记录中选出最小的前10个,用堆排序最好。如果记录数较少,则不提倡。
相关推荐
(1)数据结构与算法概念...(15)排序算法(五)——快速排序 (16)排序算法(六)——希尔排序 (17)排序算法(七)——堆排序 (18)排序算法(八)——基数排序 (19)排序算法(九)——八大排序算法总结
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
用Java实现的堆排序算法, 其中使用的是Max——heap
小白日记之八种排序算法——八种排序算法:冒泡排序、选择排序、插入排序、希尔排序、基数排序、堆排序、归并排序、快排
数据分析与算法分析,书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。
堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1...
堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1 ...
7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法 7.8 排序算法的一般下界 7.9 桶式排序 ...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
本文件讲了十种JAVA排序方法(冒泡(Bubble)排序——相邻交换 、选择排序——每次最小/大排在相应的位置 、插入排序——将下一个插入已排好的序列中 、壳(Shell)排序——缩小增量 、归并排序 、快速排序 、堆排序 ...
堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1 ...
4.7 堆排序法 116 4.7.1 堆排序算法 116 4.7.2 堆排序算法示例 121 4.8 合并排序法 123 4.8.1 合并排序算法 123 4.8.2 合并排序算法示例 126 4.9 排序算法的效率 129 4.10 排序算法的其他应用 130 4.10.1 ...
- 堆排序 - 归并排序 - 快速排序 ###第八章 -不相交集 ###第九章 -邻接表(Versioni 1,2) -拓扑排序(Versioni 1,2) -单源最短路径算法 -最大网络流 -最小生成树 -深度优先搜索 -双连通性 -欧拉回路 ###第十章 -分治...
练习 参考文献第7章 排序 7.1 预备知识 7.2 插入排序 7.2.1 算法 7.2.2 插入排序的分析 7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 ...
练习 参考文献第7章 排序 7.1 预备知识 7.2 插入排序 7.2.1 算法 7.2.2 插入排序的分析 7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 ...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
7、 堆与栈 8、 队列 9、 高级算法 九、 设计模式 1、 结构型模式 ①代理模式 ②装饰模式 ③适配器模式 2、 创建型模式 ①单例模式 3、 行为型模式 ①策略模式 ②观察者模式 4、 所有模式汇总 十、 场景题 十一、 ...
关于java程序员发展需要学习的路线整理集合 技术 应用技术 计算机基础知识 cpu mem disk net 线程,进程 第三方库 poi Jsoup zxing Gson 数据结构 树 栈 链表 队列 图 操作系统 linux 代码控制...