堆 Heap

  • 结构
  • 分析
  • 应用

堆(Heap)是一种特殊的树状结构,是二叉树的一种。它满足父节点总是大于或总是小于子节点的性质。在上一篇Dijkstra算法里提到了用堆可以进一步降低时间复杂度,常常作为堆排序(Heap Sort)出现。

结构

堆必须满足这三个条件:

  1. 堆是一个二叉树
  2. 堆的节点总是大于或小于子节点
  3. 堆中的子树也是堆

如果父节点总是大于子节点,那么这个堆是大根堆、最大堆(max-heap);如果父节点总是小于子节点,那么这个堆是小根堆、最小堆(min-heap)。

最大堆(左)& 最小堆(右)

分析

堆可以进行的操作有:插入元素、提取最小值(最大值)、删除元素和构造堆。

假设堆中有n个元素,均以最小堆为例。

  • 插入元素:先将该元素插入最末端一层,再冒泡向堆顶调整。时间复杂度为 O(\log n)
  • 提取最小值(最小堆):先删除堆顶元素,再将原堆顶的较小子节点作为新的堆顶,然后冒泡调整。时间复杂度为 O(\log n)
  • 删除元素:与提取最小值类似,时间复杂度为 O(\log n)
  • 构造堆:构建一个n个元素的堆,时间复杂度为 O(n)

堆可以用array、list来表示,一般定义节点(i)的父节点为(i/2)或([i/2]),子节点为(2i)和(2i+1)。

在Python中,有heapq库可以使用,在C++和Java中,可以用PriorityQueue。

应用

堆的应用有:堆排序、计算动态中位数和简化算法(如Dijkstra)等。

  • 堆排序

堆排序的基本思想:将待排序序列构造成一个最大堆或最小堆,再用剩下(n-1)个元素构造堆。具体可见:CNBLOGS 堆排序

它与快排(Quick Sort)类似,是不稳定的,近似时间复杂度为 O(n \log n)

  • 计算动态中位数

leetcode中有这道题目,可以进行测试:Leetcode 动态中位数。解决思想是将已输入的数组排序以中位数为中心分为两部分,第一部分为最大堆,第二部分为最小堆。具体可以看leetcode中的题解,很详细。

Python代码实现: https://github.com/xueqiwang0v0/FindMedianFromDataStream

代码可以实现动态计算中位数,但是对于leetcode中的特殊情况不能很好地处理,后续会改进。

  • 简化算法

以Dijkstra算法为例(详情见Dijkstra最短路径算法),利用堆来存储节点,成为集合X。整体时间复杂度从 \Theta(mn) 降低为 \Theta(m \log n)

参考资料

  1. 维基百科 堆
  2. Stanford算法公开课 data structures week3
  3. CSDN 堆树详解

You May Also Like

About the Author: 雪球

一个在读的工科研究生 一个努力追赶时代脚步的人 Github: https://github.com/xueqiwang0v0 LinkedIn: https://www.linkedin.com/in/xueqi-wang-0939b51a6/

发表评论

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