数据结构与算法-排序(六)堆排序(Heap Sort)

数据结构与算法-排序(六)堆排序(Heap Sort)摘要堆排序需要用到一种数据结构,大顶堆。大顶堆是一种二叉树结构,本质是父节点的数大于它的左右子节点的数,左右子节点的大小顺序不限制,也就是根节点

欢迎大家来到IT世界,在知识的湖畔探索吧!

摘要

堆排序需要用到一种数据结构,大顶堆。大顶堆是一种二叉树结构,本质是父节点的数大于它的左右子节点的数,左右子节点的大小顺序不限制,也就是根节点是最大的值。

这里就是不断的将大顶堆的根节点的元素和尾部元素交换,交换到大顶堆没有可以被交换的元素为止。后面再说大顶堆的逻辑。

逻辑

首先将序列通过大顶堆排序。然后不断的从堆中取出顶部元素放在尾部,直到大顶堆元素为空。

流程

  1. 对序列进行原地建堆操作
  2. 重复下面操作,直到堆元素数量为 1
    1. 交换堆顶元素与尾元素
    2. 堆的元素数量减 1
    3. 对 0 位置进行 1 次 自下而上的下滤

下面在代码中解释原地建堆自下而上的下滤这两个词的逻辑。

实现

首先进行原地建堆。原地建堆是先将序列按照大顶堆的排序逻辑处理序列。

大顶堆的序列逻辑是父节点的值大于它的左右子节点的值,可以想象成一个二叉树。这里的原地排序用到了siftDown方法,而且在循环中只循环到序列一半数量,为什么?这个在下面看siftDown方法时详细探究一下。


// 原地建堆
// 自下而上的下滤
heapSize = array.length;
for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
	siftDown(i);
}

欢迎大家来到IT世界,在知识的湖畔探索吧!

交换堆顶和尾部元素,然后将需要比较的序列元素数量减少1,并将要进行比较的序列再使用siftDown方法过滤,保持序列的大顶堆的性质。然后继续开始的交换,直到可以比较的序列数量为 1 就截止。

欢迎大家来到IT世界,在知识的湖畔探索吧!while (heapSize > 1) {
	// 交换堆顶元素和尾部元素
	swap(0, --heapSize);
		
	// 对 0 位置进行 siftDown(恢复堆的性质)
	siftDown(0);
}

大顶堆的siftDown方法

这里来探究一下siftDown(下滤)。

二叉树的父节点和子节点的关系符合这样的公式

leftChilder = partner * 2 + 1

rightChilder = parnter * 2 + 1 + 1

half (叶子)节点的数量是总节点数量的 1/2

siftDown 方法主要是将 index 位置上的元素放在合适的位置上。那么什么位置是合适的位置呢

依据大顶堆的父节点值大于左右子节点的值的性质来看,只要是保证 index 位置的元素大于它的左右子节点就好。

看下面代码,如果 index < half 才进行循环比较,那么就有一个问题,当 index >= half 为什么不用比较

这就要提到很巧妙的点,首先看大顶堆的性质,左右子节点没有具体顺序的要求,其次子节点的值小于父节点。那么就可以依据二叉树的叶子节点性质,如果index的位置是在叶子节点位置,那么就本来比它的父节点要小,就不用比较(这个是建立在序列本来符合大顶堆的顺序,出现一个位置的元素有变化时进行的过滤处理)。

这也是上面的原地排序中,只从一半的位置开始,是因为从这个位置开始,肯定会给它的子节点比较,过滤出大的,并放在合适位置。

代码中有三个巧妙的点

  1. 循环从序列的一半位置开始比较,如果位置不在前半部分,就不进行比较,这个在上面分析过
  2. 在比较的时候,获取到它左右子节点中最大的节点比较。在获取右子节点的时候看右子节点是否存在rightIndex<heapSize。因为大顶堆是符合完全二叉树的(尽量往左子树安排元素)。
  3. 说是二叉树,但是没有实际的节点,还是一个线性序列,通过公式来获取左右子树的位置,这个就是心中有树,没有树也是树
	
/*
 * 让 index 位置的元素下滤
 */
private void siftDown(int index) {
	E element = array[index];

	int half = heapSize >> 1; // 取出非叶子节点
	// 第一个叶子结点的索引 == 非叶子节点的数量
	// 必须保证 index 是非叶子节点
	while (index < half) {
		// index 的节点有2种情况
		// 1、只有左子节点
		// 2、同时有左右子节点
			
		// 默认左子节点跟它进行比较
		int childIndex = (index << 1) + 1;
		E child = array[childIndex];
		// 右子节点
		int rightIndex = childIndex + 1;
		if (rightIndex < heapSize && cmp(array[rightIndex], child) > 0) {
			child = array[ childIndex = rightIndex];
		}
			
		if (cmp(child, element) < 0) break;
			
		// 将子节点存放到index位置
		array[index] = child;
		// 重新设置 index
		index = childIndex;
	}
	array[index] = element;
}

时间和空间复杂度

  • 最好、平均时间复杂度:O(nlogn)
  • 最坏时间复杂度:O((nlogn)
  • 空间复杂度:O(1)
  • 属于不稳定排序

题外话

这次的排序用到了二叉树大顶堆的一些知识,可能看下来有诸多疑问,这里就先请诸位看官有个印象,后续我会分享二叉树的知识,然后在回过头来看堆排序,会让你思路大开。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/32921.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信