`
huntfor
  • 浏览: 201126 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

排序算法(3)之堆排序——java实现

 
阅读更多

堆(数据结构)的定义:

wiki百科中对堆的定义是

wikipedia 写道
堆(heap)亦被称为优先队列(priority queue),通常是一个可以被看做一棵数组对象。在队列中,调度程序反复提取队列中的第一个作业并运行,因而实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

 

既然堆是一棵树,那么其特点也应该是递归的了。继续wikipedia:

写道
堆的实现通过构造二叉堆(binary heap),实为二叉树(疑问:堆不应该只有二叉堆吧?)的一种,二叉堆是完全二叉树,性质如下:
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));
	}
}

 

 打印结果是:

写道
[9, 8, 6, 3, 5, 4, 1, 2, 7]
[1, 2, 3, 5, 4, 6, 7, 8, 9]

 从代码中可以看出,调整每个节点的时间复杂度是树的高度logN,因此简化后的时间复杂度为O(NlogN)

空间复杂度,由于存在交换键值,因此需要一个额外空间,空间复杂度为O(1)。

堆排序适合记录数很多的情况,比如从100000个记录中选出最小的前10个,用堆排序最好。如果记录数较少,则不提倡。

  • 大小: 52.5 KB
  • 大小: 129.3 KB
  • 大小: 94.4 KB
分享到:
评论

相关推荐

    最快的排序算法 图解八大排序算法——我见过的最详细的讲解(转),排序算法数据结构

    常见的排序算法有八种,即选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、.radix 排序和基数排序。 一、分类 内部排序和外部排序是两种基本的排序分类。内部排序是指待排序记录存放在计算机随机...

    各种排序算法java实现

    标题 "各种排序算法java实现" 涉及到的是计算机科学中的一个重要领域——算法,特别是排序算法在Java编程语言中的具体应用。排序算法是数据结构与算法分析中的基础部分,它们用于将一组数据按照特定顺序排列。在这个...

    数据结构与问题求解——java语言描述 源码

    例如,`Sort.java`可能包含了各种排序算法的实现,如冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等。每种排序算法都有其特定的时间复杂性和适用场景,通过阅读源码可以加深对它们的理解。 此外,...

    算法可视化系列——排序算法——选择排序

    **选择排序**是一种简单直观的排序算法,它的工作原理如下:...在实际应用中,更高效的排序算法如快速排序、归并排序或堆排序等通常会优先考虑。然而,对于教学和理解排序算法的基本原理,选择排序是一个很好的起点。

    《Java数据结构和算法》学习笔记(2)——4种简单排序算法

    在实际开发中,我们往往使用更高效的排序算法,如快速排序、归并排序、堆排序等。然而,了解并能实现这些基础排序算法,对于提升编程思维和问题解决能力大有裨益。在学习和研究过程中,可以结合工具,例如使用Java...

    数据结构与算法分析——Java语言描述

    常见的排序算法(如冒泡排序、快速排序、归并排序、堆排序)和查找算法(如线性查找、二分查找)都有详尽的解释和实例。此外,还包括动态规划、贪心算法、回溯法等高级算法思想。算法分析不仅关注实现,更强调时间...

    数据结构与算法答案——java语言描述

    本资料集是“数据结构与算法答案——java语言描述”,虽然全为英文内容,但其深入探讨了使用Java实现数据结构和算法的细节。 1. **数组**:数组是最基本的数据结构之一,它是一系列相同类型元素的集合,可以通过索...

    数据结构与算法分析——Java语言描述-带书签目录高清扫描版

    排序算法如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序,各有优缺点,适用于不同的数据特性。查找算法包括顺序查找、二分查找和哈希查找,其中哈希表提供了近乎常数时间的查找效率。此外,高级算法如...

    常用排序算法小结(附Java实现)

    文章可能涵盖了如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等多种经典的排序算法,并且通过Java代码进行了详尽的解释和实现。 1. 冒泡排序:这是一种简单的排序方法,通过重复遍历数组,比较相邻...

    选择排序算法。其中堆排序使用的时最小堆,通过改变数组下标变更堆的顶实现的

    本文将深入探讨两种特定的排序算法——选择排序和堆排序,并重点解析堆排序如何利用最小堆来实现排序过程。这两种算法在Java编程语言中都有广泛应用。 首先,我们来看选择排序。它是一种简单直观的排序算法,其基本...

    排序算法 Java经典算法

    在编程领域,排序算法是计算机科学中的核心概念,特别是在Java这样的高级编程语言中。排序算法是用来组织和优化数据结构的关键工具,它使得数据按照特定顺序排列,如升序或降序。本篇将深入探讨Java中的一些经典排序...

    排序算法(Java描述)

    本文将深入探讨两种经典的排序算法——选择排序和插入排序,并通过Java语言进行具体描述,旨在帮助读者理解这两种算法的工作原理、时间复杂度以及实际应用。 #### 选择排序:效率与简洁性的权衡 选择排序是一种简单...

    数据结构——JAVA版

    5. 排序与搜索算法:排序算法包括快速排序、归并排序、堆排序等,搜索算法则包括二分搜索等。在Java中,排序可以利用Arrays.sort方法实现,搜索则可以通过Collections.binarySearch方法完成。 除了上述数据结构,书...

    排序算法合集(Java)

    4. **堆排序**:堆排序是一种基于比较的排序算法,利用了数据结构——二叉堆。它首先将数组转换成一个最大堆或最小堆,然后将堆顶元素与末尾元素交换,缩小堆的大小,并重新调整堆。这个过程反复进行,直到堆的大小...

    Java数据结构和算法

    (1)数据结构与算法概念...(15)排序算法(五)——快速排序 (16)排序算法(六)——希尔排序 (17)排序算法(七)——堆排序 (18)排序算法(八)——基数排序 (19)排序算法(九)——八大排序算法总结

    java实现各种排序算法及其速度对比(附详细代码)(csdn)————程序.pdf

    本文将详细讲解Java中实现的各种排序算法,并对比它们的性能。 1. **Java自带的排序** Java 提供了一个内置的排序方法 `Arrays.sort()`,它使用了TimSort算法,一种混合排序算法,结合了插入排序和归并排序的优点...

    常用排序算法分析与实现(Java版)

    在IT领域,排序算法是计算机科学的基础之一,尤其在编程语言如Java中,理解并掌握各种排序算法至关重要。本文将深入探讨几种常见的排序算法,并提供它们的Java实现,旨在帮助开发者提升算法理解和应用能力。 首先,...

    java面试java排序算法

    在Java面试中,排序算法是常见的话题,因为它在实际编程中有着广泛的应用。这里我们将讨论两种常见的排序算法:归并排序和堆排序。 首先,让我们深入理解归并排序(Merge Sort)。归并排序是一种分治策略,其基本...

Global site tag (gtag.js) - Google Analytics