内容简介:堆排序是一个很重要的排序算法,它是高效率的排序算法,复杂度是O(nlogn),堆排序不仅是面试进场考的重点,而且在很多实践中的算法会用到它,比如经典的TopK算法、小顶堆用于实现优先级队列。堆排序是利用堆这种数据结构所设计的一种排序算法。堆实际上是一个完全二叉树结构。问:那么什么是完全二叉树呢?
堆基本概念
堆排序是一个很重要的 排序 算法,它是高效率的排序算法,复杂度是O(nlogn),堆排序不仅是面试进场考的重点,而且在很多实践中的算法会用到它,比如经典的TopK算法、小顶堆用于实现优先级队列。
堆排序是利用堆这种数据结构所设计的一种排序算法。堆实际上是一个完全二叉树结构。
问:那么什么是完全二叉树呢?
答:假设一个二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
我们知道堆是一个完全二叉树了,那么堆又分两种堆: 大顶堆 和 小顶堆
它们符合一个重要的性质:
-
小顶堆满足:Key[i] <= key[2i+1] && Key[i] <= key[2i+2]
-
大顶堆满足:Key[i] >= Key[2i+1] && key >= key[2i+2]
怎么理解呢,其实很简单,顾名思义,大顶堆最大的元素在跟节点,堆的性质决定了大顶堆中节点一定大于等于其子节点,反之,小顶堆的最小元素在根节点。我们来看看大顶堆和小顶堆的示意图:
堆排序基本思想及步骤
堆排序有以下几个核心的步骤:
-
将待排序的数组初始化为大顶堆,该过程即建堆。
-
将堆顶元素与最后一个元素进行交换,除去最后一个元素外可以组建为一个新的大顶堆。
-
由于第二部堆顶元素跟最后一个元素交换后,新建立的堆不是大顶堆,需要重新建立大顶堆。重复上面的处理流程,直到堆中仅剩下一个元素。
假设我们有一个待排序的数组 arr = [4, 6, 7, 2, 9, 8, 3, 5], 我们把这个数组构造成为一个二叉树,如下图:
问:此时我们需要把这个完全二叉树构造成一个大顶堆,怎么构造呢?
答:一个很好的方法是遍历二叉树的非叶子节点 自下往上 的构造大顶堆,针对每个非叶子节点,都跟它的左右子节点比较,把最大的值换到这个子树的父节点。
问:为什么要从非叶子节点开始,而不是从最后一个节点开始?
答:因为叶子节点下面没有子节点了,就没必要操作了。
问:为什么要从下往上而不是从上往下遍历非叶子节点?
答:我们从下面开始遍历调整每个节点成为它左右节点的最大值,那么一直往上的话,最后根节点一定是最大的值;但是如果我们从上往下,上面满足了大顶堆,下面不满足,调整后,上面可能又不满足了,所以从下往上是最好的方案。
那么我们构造的大顶堆的代码就很明显了:
# 构造大顶堆,从非叶子节点开始倒序遍历,因此是l//2 -1 就是最后一个非叶子节点 l = len(arr) for i in range(l//2-1, -1, -1): build_heap() # 遍历针对每个非叶子节点构造大顶堆
看我们的例子,非叶子节点有2, 8, 6, 4, 我们从最后一个非叶子节点,也就是5开始遍历构造大顶堆,2 跟 5 比较,5比较大,所以把 arr[3]和arr[7]从数组中交换一下位置,那么就完成第一个非叶子节点的置换。下面的节点继续交换
此时9跟4交换后,4这个节点下面的树就不是不符合大顶堆了,所以要针对4这个节点跟它的左右节点再次比较,置换成较大的值,4跟左右子节点比较后,应该跟6交换位置。
那么至此,整个二叉树就是一个完完整整的大顶堆了,每个节点都不小于左右子节点。
此时我们把堆的跟节点,即数组最大值9跟数组最后一个元素2交换位置,那么9就是排好序的放在了数组最后一个位置
2到了跟节点后,新的堆不满足大顶堆,我们需要重复上面的步骤,重新构造大顶堆,然后把大顶堆根节点放到二叉树后面作为排好序的数组放好。就这样利用大顶堆一个一个的数字排好序。
值得注意的一个地方是,上面我们把9和2交换位置后,2处于二叉树根节点,2需要跟右子树8交换位置,交换完位置后,右子树需要重新 递归 调整大顶堆,但是左子树6这边,已经是满足大顶堆属性,因为不需要再操作。
代码实现:
class Solution(object): def heap_sort(self, nums): i, l = 0, len(nums) self.nums = nums # 构造大顶堆,从非叶子节点开始倒序遍历,因此是l//2 -1 就是最后一个非叶子节点 for i in range(l//2-1, -1, -1): self.build_heap(i, l-1) # 上面的循环完成了大顶堆的构造,那么就开始把根节点跟末尾节点交换,然后重新调整大顶堆 for j in range(l-1, -1, -1): nums[0], nums[j] = nums[j], nums[0] self.build_heap(0, j-1) return nums def build_heap(self, i, l): """构建大顶堆""" nums = self.nums left, right = 2*i+1, 2*i+2 ## 左右子节点的下标 large_index = i if left <= l and nums[i] < nums[left]: large_index = left if right <= l and nums[left] < nums[right]: large_index = right # 通过上面跟左右节点比较后,得出三个元素之间较大的下标,如果较大下表不是父节点的下标,说明交换后需要重新调整大顶堆 if large_index != i: nums[i], nums[large_index] = nums[large_index], nums[i] self.build_heap(large_index, l)
堆排序复杂度
时间复杂度, 包括两个方面:
-
初始化建堆过程时间:O(n)
-
更改堆元素后重建堆时间:O(nlogn),循环 n -1 次,每次都是从根节点往下循环查找,所以每一次时间是 logn,总时间:logn(n-1) = nlogn - logn ,所以复杂度是 O(nlogn)
时间复杂度:O(nlogn)
空间复杂度:因为堆排序是就地排序,空间复杂度为常数:O(1)
堆排序的应用:TopK算法
面试中经常考的一个面试题就是,如果在海量数据中找出最大的100个数字,看到这个问题,可能大家首先会想到的是使用高效排序算法,比如快排,对这些数据排序,时间复杂度是O(nlogn),然后取出最大的100个数字。但是如果数据量很大,一个机器的内存不足以一次过读取这么多数据,就不能使用这个方法了。
不使用分布式机器计算,使用一个机器也能找出TopK的经典算法就是使用堆排序了,具体方法是:
维护一个大小为 K 的 小顶堆 ,依次将数据放入堆中,当堆的大小满了的时候,只需要将堆顶元素与下一个数比较:
-
如果小于堆顶元素,则直接忽略,比较下一个元素;
-
如果大于堆顶元素,则将当前的堆顶元素抛弃,并将该元素插入堆中。遍历完全部数据,Top K 的元素也自然都在堆里面了。
整个操作中,遍历数组需要O(n)的时间复杂度,每次调整小顶堆的时间复杂度是O(logK),加起来就是 O(nlogK) 的复杂度,如果 K 远小于 n 的话, O(nlogK) 其实就接近于 O(n) 了,甚至会更快,因此也是十分高效的。
总结
堆排序有以下几个核心的步骤:
-
将待排序的数组初始化为大顶堆,该过程即建堆。
-
将堆顶元素与最后一个元素进行交换,除去最后一个元素外可以组建为一个新的大顶堆。
-
由于第二部堆顶元素跟最后一个元素交换后,新建立的堆不是大顶堆,需要重新建立大顶堆。重复上面的处理流程,直到堆中仅剩下一个元素。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 【JS面试向】选择排序、桶排序、冒泡排序和快速排序简介
- 数据结构和算法面试题系列—排序算法之快速排序
- 数据结构和算法面试题系列—排序算法之基础排序
- 前端面试常考的10大排序算法
- 面试常考排序算法的全面总结
- 拜托,面试别再问我桶排序了
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Growth Hack 這樣做
Xdite / PCuSER電腦人文化 / 2016-5-7 / 300.00台幣
◎具體教你在預算有限的情況之下,把成長做出來的可行與必要方法! ◎帶動台灣成長駭客話題的專業講師,親授讓產品突破80分的成長秘笈 @這本書要給誰看? 1. 創業者、個人品牌經營者,想要提高自己服務轉換率的人。 2. 空有產品,但是賣不出去,花了錢投廣告卻效果低落的人。 @這本書有什麼不一樣? 1.全球最重要的趨勢,台灣最知名的 Growth Hack 講師 Xd......一起来看看 《Growth Hack 這樣做》 这本书的介绍吧!