三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)

栏目: IT技术 · 发布时间: 4年前

内容简介:堆排序是一个很重要的排序算法,它是高效率的排序算法,复杂度是O(nlogn),堆排序不仅是面试进场考的重点,而且在很多实践中的算法会用到它,比如经典的TopK算法、小顶堆用于实现优先级队列。堆排序是利用堆这种数据结构所设计的一种排序算法。堆实际上是一个完全二叉树结构。问:那么什么是完全二叉树呢?

堆基本概念

堆排序是一个很重要的 排序 算法,它是高效率的排序算法,复杂度是O(nlogn),堆排序不仅是面试进场考的重点,而且在很多实践中的算法会用到它,比如经典的TopK算法、小顶堆用于实现优先级队列。

堆排序是利用堆这种数据结构所设计的一种排序算法。堆实际上是一个完全二叉树结构。

问:那么什么是完全二叉树呢?

答:假设一个二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)
完全二叉树

我们知道堆是一个完全二叉树了,那么堆又分两种堆: 大顶堆小顶堆

它们符合一个重要的性质:

  • 小顶堆满足:Key[i] <= key[2i+1] && Key[i] <= key[2i+2]

  • 大顶堆满足:Key[i] >= Key[2i+1] && key >= key[2i+2]

怎么理解呢,其实很简单,顾名思义,大顶堆最大的元素在跟节点,堆的性质决定了大顶堆中节点一定大于等于其子节点,反之,小顶堆的最小元素在根节点。我们来看看大顶堆和小顶堆的示意图:

三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)
大顶堆和小顶堆

堆排序基本思想及步骤

堆排序有以下几个核心的步骤:

  1. 将待排序的数组初始化为大顶堆,该过程即建堆。

  2. 将堆顶元素与最后一个元素进行交换,除去最后一个元素外可以组建为一个新的大顶堆。

  3. 由于第二部堆顶元素跟最后一个元素交换后,新建立的堆不是大顶堆,需要重新建立大顶堆。重复上面的处理流程,直到堆中仅剩下一个元素。

假设我们有一个待排序的数组 arr = [4, 6, 7, 2, 9, 8, 3, 5], 我们把这个数组构造成为一个二叉树,如下图:

三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)
数组构造成完全二叉树

问:此时我们需要把这个完全二叉树构造成一个大顶堆,怎么构造呢?

答:一个很好的方法是遍历二叉树的非叶子节点 自下往上 的构造大顶堆,针对每个非叶子节点,都跟它的左右子节点比较,把最大的值换到这个子树的父节点。

问:为什么要从非叶子节点开始,而不是从最后一个节点开始?

答:因为叶子节点下面没有子节点了,就没必要操作了。

问:为什么要从下往上而不是从上往下遍历非叶子节点?

答:我们从下面开始遍历调整每个节点成为它左右节点的最大值,那么一直往上的话,最后根节点一定是最大的值;但是如果我们从上往下,上面满足了大顶堆,下面不满足,调整后,上面可能又不满足了,所以从下往上是最好的方案。

那么我们构造的大顶堆的代码就很明显了:

# 构造大顶堆,从非叶子节点开始倒序遍历,因此是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]从数组中交换一下位置,那么就完成第一个非叶子节点的置换。下面的节点继续交换

三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)
三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)
三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)
三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)

此时9跟4交换后,4这个节点下面的树就不是不符合大顶堆了,所以要针对4这个节点跟它的左右节点再次比较,置换成较大的值,4跟左右子节点比较后,应该跟6交换位置。

三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)

那么至此,整个二叉树就是一个完完整整的大顶堆了,每个节点都不小于左右子节点。

此时我们把堆的跟节点,即数组最大值9跟数组最后一个元素2交换位置,那么9就是排好序的放在了数组最后一个位置

三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)

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)

堆排序复杂度

时间复杂度, 包括两个方面:

  1. 初始化建堆过程时间:O(n)

  2. 更改堆元素后重建堆时间: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 的元素也自然都在堆里面了。

    三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)
    三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)

整个操作中,遍历数组需要O(n)的时间复杂度,每次调整小顶堆的时间复杂度是O(logK),加起来就是 O(nlogK) 的复杂度,如果 K 远小于 n 的话, O(nlogK) 其实就接近于 O(n) 了,甚至会更快,因此也是十分高效的。

总结

堆排序有以下几个核心的步骤:

  1. 将待排序的数组初始化为大顶堆,该过程即建堆。

  2. 将堆顶元素与最后一个元素进行交换,除去最后一个元素外可以组建为一个新的大顶堆。

  3. 由于第二部堆顶元素跟最后一个元素交换后,新建立的堆不是大顶堆,需要重新建立大顶堆。重复上面的处理流程,直到堆中仅剩下一个元素。

三分钟玩转堆排序原理及面试题(多图解释 + Python 实现)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

ODPS权威指南

ODPS权威指南

李妹芳 / 人民邮电出版社 / 2014-12 / 69元

ODPS(Open Data Processing Service)是阿里巴巴自主研发的海量数据处理和分析的服务平台,主要应用于数据分析、海量数据统计、数据挖掘、机器学习和商业智能等领域。目前,ODPS不仅在阿里内部得到广泛应用,享有很好的口碑,正逐步走向第三方开放市场。 本书是学习和掌握ODPS的权威指南,作者来自阿里ODPS团队。全书共13章,主要内容包括:ODPS入门、整体架构、数据通......一起来看看 《ODPS权威指南》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具