文档章节

堆排序详解

fengsehng
 fengsehng
发布于 2016/11/09 09:11
字数 2496
阅读 5
收藏 0

概述

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

什么是堆?

堆(二叉堆)可以视为一棵完全的二叉树,完全二叉树的一个“优秀”的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示(普通的一般的二叉树通常用链表作为基本容器表示),每一个结点对应数组中的一个元素。

如下图,是一个堆和数组的相互关系

这里写图片描述
堆和数组的相互关系
堆和数组的相互关系
对于给定的某个结点的下标 i,可以很容易的计算出这个结点的父结点、孩子结点的下标:
Parent(i) = floor(i/2),i 的父节点下标
Left(i) = 2i,i 的左子节点下标
Right(i) = 2i + 1,i 的右子节点下标
这里写图片描述

二叉堆一般分为两种:最大堆和最小堆。

分类

大根堆和小根堆:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆,又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆,又称最大堆。注意:①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆。

高度

堆可以被看成是一棵树,结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目;定义堆的高度为树根的高度。我们将看到,堆结构上的一些基本操作的运行时间至多是与树的高度成正比,为O(lgn)。

堆排序原理

堆排序就是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束。

在堆中定义以下几种操作:

最大堆调整(Max-Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
创建最大堆(Build-Max-Heap):将堆所有数据重新排序,使其成为最大堆
堆排序(Heap-Sort):移除位在第一个数据的根节点,并做最大堆调整的递归运算
继续进行下面的讨论前,需要注意的一个问题是:数组都是 Zero-Based,这就意味着我们的堆数据结构模型要发生改变

相应的,几个计算公式也要作出相应调整:
Parent(i) = floor((i-1)/2),i 的父节点下标
Left(i) = 2i + 1,i 的左子节点下标
Right(i) = 2(i + 1),i 的右子节点下标
最大堆调整(MAX‐HEAPIFY)的作用是保持最大堆的性质,是创建最大堆的核心子程序,作用过程如图所示:
这里写图片描述

由于一次调整后,堆仍然违反堆性质,所以需要递归的测试,使得整个堆都满足堆性质
通常来说,递归主要用在分治法中,而这里并不需要分治。而且递归调用需要压栈/清栈,和迭代相比,性能上有略微的劣势。

创建最大堆(Build-Max-Heap)的作用是将一个数组改造成一个最大堆,接受数组和堆大小两个参数,Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组,建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质,所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。如果最大堆的数量元素是 n,那么 Build-Max-Heap 从 Parent(n) 开始,往上依次调用 Max-Heapify。流程如下:

这里写图片描述

堆排序(Heap-Sort)是堆排序的接口算法,Heap-Sort先调用Build-Max-Heap将数组改造为最大堆,然后将堆顶和堆底元素交换,之后将底部上升,最后重新调用Max-Heapify保持最大堆性质。由于堆顶元素必然是堆中最大的元素,所以一次操作之后,堆中存在的最大元素被分离出堆,重复n-1次之后,数组排列完毕。整个流程如下:

这里写图片描述

思想

堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

(1)用大根堆排序的基本思想

① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区

② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key

③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。

(2)大根堆排序算法的基本操作:

①建堆,建堆是不断调整堆的过程,从len/2处开始调整,一直到第一个节点,此处len是堆中元素的个数。建堆的过程是线性的过程,从len/2到0处一直调用调整堆的过程,相当于o(h1)+o(h2)…+o(hlen/2) 其中h表示节点的深度,len/2表示节点的个数,这是一个求和的过程,结果是线性的O(n)。

②调整堆:调整堆在构建堆的过程中会用到,而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i),选出三者最大(或者最小)者,如果最大(小)值不是节点i而是它的一个孩子节点,那边交互节点i和该节点,然后再调用调整堆过程,这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系,是lgn的操作,因为是沿着深度方向进行调整的。

③堆排序:堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换),将前面len-1个节点继续进行堆调整的过程,然后再将根节点取出,这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)(调用一次);调整堆的时间复杂度是lgn,调用了n-1次,所以堆排序的时间复杂度是O(nlgn)[2]

代码

public class HeapSort{
private static int[] sort=new int[]{1,0,10,20,3,5,6,4,9,8,12,
17,34,11};

public static void main(String[] args){
buildMaxHeapify(sort);
heapSort(sort);
print(sort);
}

private static void buildMaxHeapify(int[] data){
//没有子节点的才需要创建最大堆,从最后一个的父节点开始
int startIndex=getParentIndex(data.length-1);
//从尾端开始创建最大堆,每次都是正确的堆
for(int i=startIndex;i>=0;i--){
maxHeapify(data,data.length,i);
}
}

/** *创建最大堆 * *@paramdata *@paramheapSize需要创建最大堆的大小,一般在sort的时候用到,因为最多值放在末尾,末尾就不再归入最大堆了 *@paramindex当前需要创建最大堆的位置 */
private static void maxHeapify(int[] data,int heapSize,int index){
//当前点与左右子节点比较
int left=getChildLeftIndex(index);
int right=getChildRightIndex(index);

int largest=index;
if(left<heapSize&&data[index]<data[left]){
largest=left;
}
if(right<heapSize&&data[largest]<data[right]){
largest=right;
}
//得到最大值后可能需要交换,如果交换了,其子节点可能就不是最大堆了,需要重新调整
if(largest!=index){
int temp=data[index];
data[index]=data[largest];
data[largest]=temp;
maxHeapify(data,heapSize,largest);
}
}

/** *排序,最大值放在末尾,data虽然是最大堆,在排序后就成了递增的 * *@paramdata */
private static void heapSort(int[] data){
//末尾与头交换,交换后调整最大堆
for(int i=data.length-1;i>0;i--){
int temp=data[0];
data[0]=data[i];
data[i]=temp;
maxHeapify(data,i,0);
}
}

/** *父节点位置 * *@paramcurrent *@return */
private static int getParentIndex(int current){
return(current-1)>>1;
}

/** *左子节点position注意括号,加法优先级更高 * *@paramcurrent *@return */
private static int getChildLeftIndex(int current){
return(current<<1)+1;
}

/** *右子节点position * *@paramcurrent *@return */
private static int getChildRightIndex(int current){
return(current<<1)+2;
}

private static void print(int[] data){
int pre=-2;
for(int i=0;i<data.length;i++){
if(pre<(int)getLog(i+1)){
pre=(int)getLog(i+1);
System.out.println();
}
System.out.print(data[i]+"|");
}
}

/** *以2为底的对数 * *@paramparam *@return */
private static double getLog(double param){
return Math.log(param)/Math.log(2);
}
}

稳定性

它是不稳定的排序方法。(排序的稳定性是指如果在排序的序列中,存在前后相同的两个元素的话,排序前 和排序后他们的相对位置不发生变化)

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述
参考:
http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
私信 提问
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
0
0
HeapSort堆排序详解

本文我们来学习下堆排序的实现原理,堆排序顾名思义就是利用了堆的特点来实现排序,首先了解堆是什么? 堆相关的一些概念 二叉树 二叉树是每个节点最多有两个子树的树结构。也就是一个节点只...

激情的狼王丶21
2018/01/19
0
0
Python天天美味(32) - python数据结构与算法之堆排序

1. 选择排序 选择排序原理是先选出最小的数,与第一个数交换,然后从第二个数开始再选择最小的数与第二个数交换,…… def selection_sort(data): for i in range(len(data) - 1): min = dat...

zting科技
2017/01/11
0
0
插入排序,希尔排序,堆排序详解

本文将介绍三种排序算法--插入排序,希尔排序,堆排序。本文所有例子都是使用升序 一.插入排序 算法思想 维护一个有序数组,将要插入的数据与有序数组自最后一个元素直到合适位置的数一一比较...

crazys_蘑菇
2018/06/29
0
0
【编程能力不行?那就写啊!】堆排序详解

正文之前 最近终于状态恢复,所以兴致很高的来解决下前阵子堆积的一些知识输出问题。本文就专讲堆排序,以前一直是冒泡排序的时代,这次就来个效率更高的,确实堆排序虽然代码比冒泡复杂了五...

HustWolf
2017/12/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Nextjs+React非页面组件SSR渲染

@随风溜达的向日葵 Nextjs Nextjs是React生态中非常受欢迎的SSR(server side render——服务端渲染)框架,只需要几个步骤就可以搭建一个支持SSR的工程(_Nextjs_的快速搭建见Next.js入门)...

随风溜达的向日葵
49分钟前
0
0
如何在 Linux 系统查询机器最近重启时间

在你的 Linux 或类 UNIX 系统中,你是如何查询系统上次重新启动的日期和时间?怎样显示系统关机的日期和时间? last 命令不仅可以按照时间从近到远的顺序列出该会话的特定用户、终端和主机名...

来来来来来
今天
3
0
Redis协议是什么样的

前言 我们用过很多redis的客户端,有没有相过自己撸一个redis客户端? 其实很简单,基于socket,监听6379端口,解析数据就可以了。 redis协议 解析数据的过程主要依赖于redis的协议了。 我们...

春哥大魔王的博客
今天
6
0
乱入Linux界的我是如何学习的

欢迎来到建哥学Linux,咳!咳!咳!开个玩笑哈,我是一个IT男,IT界的入门选手,正在学习Linux。 在之前,一直想进军IT界,学习IT技术,但是苦于没有人指导,也不知道学什么,最开始我自己在...

linuxCool
今天
4
0
携程Apollo统一配置中心的搭建和使用(java)

一.Apollo配置中心介绍 1、What is Apollo 1.1 Apollo简介 Apollo(阿波罗)是携程框架部门研发的开源配置管理中心,能够集中化管理应用不同环境、不同集群的配置,配置修改后能够实时推送到...

morpheusWB
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部