堆(数据结构)的定义:
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个,用堆排序最好。如果记录数较少,则不提倡。
相关推荐
常见的排序算法有八种,即选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、.radix 排序和基数排序。 一、分类 内部排序和外部排序是两种基本的排序分类。内部排序是指待排序记录存放在计算机随机...
标题 "各种排序算法java实现" 涉及到的是计算机科学中的一个重要领域——算法,特别是排序算法在Java编程语言中的具体应用。排序算法是数据结构与算法分析中的基础部分,它们用于将一组数据按照特定顺序排列。在这个...
例如,`Sort.java`可能包含了各种排序算法的实现,如冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等。每种排序算法都有其特定的时间复杂性和适用场景,通过阅读源码可以加深对它们的理解。 此外,...
**选择排序**是一种简单直观的排序算法,它的工作原理如下:...在实际应用中,更高效的排序算法如快速排序、归并排序或堆排序等通常会优先考虑。然而,对于教学和理解排序算法的基本原理,选择排序是一个很好的起点。
在实际开发中,我们往往使用更高效的排序算法,如快速排序、归并排序、堆排序等。然而,了解并能实现这些基础排序算法,对于提升编程思维和问题解决能力大有裨益。在学习和研究过程中,可以结合工具,例如使用Java...
常见的排序算法(如冒泡排序、快速排序、归并排序、堆排序)和查找算法(如线性查找、二分查找)都有详尽的解释和实例。此外,还包括动态规划、贪心算法、回溯法等高级算法思想。算法分析不仅关注实现,更强调时间...
本资料集是“数据结构与算法答案——java语言描述”,虽然全为英文内容,但其深入探讨了使用Java实现数据结构和算法的细节。 1. **数组**:数组是最基本的数据结构之一,它是一系列相同类型元素的集合,可以通过索...
排序算法如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序,各有优缺点,适用于不同的数据特性。查找算法包括顺序查找、二分查找和哈希查找,其中哈希表提供了近乎常数时间的查找效率。此外,高级算法如...
文章可能涵盖了如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等多种经典的排序算法,并且通过Java代码进行了详尽的解释和实现。 1. 冒泡排序:这是一种简单的排序方法,通过重复遍历数组,比较相邻...
本文将深入探讨两种特定的排序算法——选择排序和堆排序,并重点解析堆排序如何利用最小堆来实现排序过程。这两种算法在Java编程语言中都有广泛应用。 首先,我们来看选择排序。它是一种简单直观的排序算法,其基本...
在编程领域,排序算法是计算机科学中的核心概念,特别是在Java这样的高级编程语言中。排序算法是用来组织和优化数据结构的关键工具,它使得数据按照特定顺序排列,如升序或降序。本篇将深入探讨Java中的一些经典排序...
本文将深入探讨两种经典的排序算法——选择排序和插入排序,并通过Java语言进行具体描述,旨在帮助读者理解这两种算法的工作原理、时间复杂度以及实际应用。 #### 选择排序:效率与简洁性的权衡 选择排序是一种简单...
5. 排序与搜索算法:排序算法包括快速排序、归并排序、堆排序等,搜索算法则包括二分搜索等。在Java中,排序可以利用Arrays.sort方法实现,搜索则可以通过Collections.binarySearch方法完成。 除了上述数据结构,书...
4. **堆排序**:堆排序是一种基于比较的排序算法,利用了数据结构——二叉堆。它首先将数组转换成一个最大堆或最小堆,然后将堆顶元素与末尾元素交换,缩小堆的大小,并重新调整堆。这个过程反复进行,直到堆的大小...
(1)数据结构与算法概念...(15)排序算法(五)——快速排序 (16)排序算法(六)——希尔排序 (17)排序算法(七)——堆排序 (18)排序算法(八)——基数排序 (19)排序算法(九)——八大排序算法总结
本文将详细讲解Java中实现的各种排序算法,并对比它们的性能。 1. **Java自带的排序** Java 提供了一个内置的排序方法 `Arrays.sort()`,它使用了TimSort算法,一种混合排序算法,结合了插入排序和归并排序的优点...
在IT领域,排序算法是计算机科学的基础之一,尤其在编程语言如Java中,理解并掌握各种排序算法至关重要。本文将深入探讨几种常见的排序算法,并提供它们的Java实现,旨在帮助开发者提升算法理解和应用能力。 首先,...
在Java面试中,排序算法是常见的话题,因为它在实际编程中有着广泛的应用。这里我们将讨论两种常见的排序算法:归并排序和堆排序。 首先,让我们深入理解归并排序(Merge Sort)。归并排序是一种分治策略,其基本...