经典算法巡礼(七) -- 排序之堆排序

一、优先队列


很多时候,我们需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。比如你可能启动了若干个定时器,那么下一次处理定时器事件只需要考虑距离现在时间最近的定时器即可,定时器触发时间无须全部有序,只需要处理优化级最高的定时器即可。

这种情况下,一个合适的数据结构应该支持两种操作:删除最小元素插入元素。而且这两种操作的效率应该在可接受范围之内。这种数据类型叫优先队列

二、堆的定义


二叉堆能够很好的实现优先队列的基本操作。在二叉堆中,每个元素都要保证大于等于它的孩子结点。相应的,这些孩子结点同样要大于等于它们的孩子结点,以此类推。当然,这样的二叉堆又称最大堆。与最大堆类似,若每个元素均小于等于它的孩子结点,则称最小堆。之前提到的定时器触发问题,它所适合的数据结构应该为最小堆。

三、二叉堆表示法


二叉堆是完全二叉树,因此可以只用数组来表示二叉堆。具体方法是将二叉树的结点按照层级顺序放入数组中,根结点放在位置1,它的子结点放在位置2和3,而子结点的子结点则放在位置4,5,6,7,以此类推。而事实上,很容易就可以在数组中表示二叉树,即位置k的结点,它的子结点在数组中的位置则为2k和2k+1。

四、堆的操作


在堆的有序化过程中,我们会碰到以下两种情况:

  • 当某个结点的优先级上升(或者在堆底中加入一个新的元素)时,我们需要由下至上恢复堆的有序性;
  • 当某个结点的优先级下降(比如根结点被替换为一个新的元素)时,我们需要由上至下恢复堆的有序列性。

为了解决以上两个问题,就有了下面将要描述的上浮(swin)下沉(sink)操作。

由下至上的有序化(上浮)

由于某结点的变化,造成了该结点比它的父结点更大(最大堆情况),从而影响了堆的有序性。比如堆中有新的元素加入堆底,而该新加入元素又比它的父结点更大,则需要将其与它的父结点交换位置,从而恢复它及其父结点的有序性。当然,这个过程会不停重复,直至堆中元素全部有序为止。整个过程就是之前所说的由下至上的上浮过程。具体golang可参考如下:

	func (this *HeapPQ) swim(idx int) {
		for idx > 1 && this.less(idx/2, idx) == true {
			this.exch(idx/2, idx)
			idx /= 2
		}
	}

由上至下的有序化(下沉)

由于某结点的变化,造成了该结点比它的子结点更小(最大堆情况),从而影响了堆的有序性。比如删除堆中根结点的元素,并原先在堆底的元素放置于根结点位置。事实上这就是最大堆中取最大元素的操作。当然,为了保持堆的有序性,则对新的根结点进行下沉操作,若根结点比它的子结点中的任意一个小,则将根结点与此结点交换,同时将该子结点进行重复操作,直到堆恢复有序性为止。整个过程就是之前的说的由上至下的下沉过程。具体golang可参考如下:

	func (this *HeapPQ) sink(idx int) {
		for 2*idx <= this.Size() {
			child := 2 * idx
			if child < this.Size() && this.less(child, child+1) == true {
				child++
			}
			if this.less(idx, child) != true {
				break
			}
			this.exch(idx, child)
			idx = child
		}
	}

五、堆排序


堆排序可以分为两个阶段:

  • 堆的构造阶段
  • 下沉排序阶段

构造一个堆,可以用以下两种方法进行。第一种,从左至右遍历数组,用swin()保证扫描指针左侧的所有元素已经是一棵堆有序的完全树即可。第二种,事实上是更聪明更高效的方法。就是从右至左用sink()函数构造子堆。开始时我们只需要扫描数组中的一半元素,所以是更高效的方法。

第二个阶段,即下沉排序阶段,我们可以将堆中最大元素删除,然后放入堆缩小后数组空出的位置。

整个过程用代码表述如下:

	func (this *HeapSort) sink(a []Comparable, i int, j int, compare Compare) {
		b := a[i:j]
		b = append(make([]Comparable, 1), b...)
		size := len(b) - 1

		func(idx int) {
			for 2*idx <= size {
				child := 2 * idx
				// fmt.Println(idx, child, size)
				if child < size && compare(b[child], b[child+1]) < 0 {
					child++
				}
				if compare(b[idx], b[child]) < 0 {
					this.exch(b, idx, child)
					idx = child
					continue
				}
				break
			}
		}(1)

		copy(a[i:j], b[1:])
	}

	// Sort中参数类型Comparable为统一的可比较接口,若为整数数组排序,则Comparable为int即可
	// Sort中参数类型Compare为配合Comparable接口的比较方法,若为整数数组排序,则Compare即满足a int < a int即可
	func (this *HeapSort) Sort(a []Comparable, compare Compare) {
		n := len(a)

		// 堆构造
		for i := n / 2; i >= 0; i-- {
			this.sink(a, i, n, compare)
		}

		// 堆排序的下沉阶段
		for i := n - 1; i > 1; {
			this.exch(a, 0, i)
			i--
			this.sink(a, 0, i, compare)
		}
	}

至于堆排序的效率,在sink()函数中,比较操作最多进行2logN次,所以排序整个数组最多需要N*2logN次比较操作,因此堆排序的时间复杂度为O(NlogN),所以可以用于大规模数据的排序。

堆排序是能够同时最优地利用空间和时间的方法,即使在最坏的情况下,它也能保证使用~2NlogN次比较和恒定的额外空间。但现代系统的许多应用很少使用它,因为堆排序无法有效利用缓存。数组元素很少和相邻的其他元素进行比较,因此缓存未命中的次数要远远高于大多数比较都在相邻元素间进行的算法,如快速排序,归并排序,甚至是希尔排序(希尔排序算是没有多少相信元素间的比较的算法了)。

但是,用堆实现优先队列在现代应用程序中却起着重要的作用,因为它能在插入操作和删除最大元素操作保证对数级别的运行时间(logN)

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Spark学习技巧

JAVA集合框架中的常用集合及其特点、适用场景、实现原理简介

1663
来自专栏小狼的世界

Binary Search Tree 以及一道 LeetCode 题目

由于对于 Binary search tree 不理解,所以绕了点弯路,要解这道题,必须理解什么是 binary search tree。我们来看一下定义:

1082
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

1153
来自专栏恰童鞋骚年

剑指Offer面试题:24.复杂链表的复制

  下图是一个含有5个结点的复杂链表。图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,指向NULL的指针没有画出。

832
来自专栏计算机视觉与深度学习基础

Leetcode 179 Largest Number

Given a list of non negative integers, arrange them such that they form the lar...

25610
来自专栏Java工程师日常干货

对HashMap的思考及手写实现前言对HashMap的思考通过写一个迷你版的HashMap来深刻理解

HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设...

1002
来自专栏小灰灰

Java容器篇小结之List自问自答

I. List篇 0. 什么是List 看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂 列表,什么是列表呢? 好比你到了一个村里,看...

2218
来自专栏程序员互动联盟

【C++练手】C++实现单链表

前几天找实习的时候,一个面试官给我留了一个题,做一个链表demo,要求实现创建、插入、删除等操作。 链表是一种常见的数据结构,它是一种物理存储单元上非连续、非顺...

3447
来自专栏阿杜的世界

Java并发-CopyOnWriteArrayList前言CopyOnWriteArrayList API例子1:插入(删除)数据的同时进行遍历例子2:不支持一边遍历一边删除结论参考资料

今天我们一起学习下java.util.concurrent并发包里的CopyOnWriteArrayList工具类。当有多个线程可能同时遍历、修改某个公共数组时...

1513
来自专栏计算机视觉与深度学习基础

Leetcode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth larg...

22310

扫码关注云+社区

领取腾讯云代金券