Data Structure 05 - Heap
# 前置知识
在阅读本文档前,请确保你已经掌握二叉树的基础知识,详见 Data Structure 知识板块中的 04 - Binary Tree 文档。
# 基本概念
堆 (Heap) 是一种满足堆属性的树或森林。我们称堆上每个节点上的元素值为节点的 键值 (key) 。
如果在树上(或森林中)任取一个节点 ,对于 的任意一个子节点 , 的键值一定大于等于(或小于等于) 的键值,则称该树(或森林)满足 堆属性 (heap property) ,并称该树(或森林)为堆。
如果上述节点间关系为大于等于,则称这个堆为 大顶堆 (max heap) ;如果为小于等于,则称这个堆为 小顶堆 (min heap) 。堆的根节点被称为 堆顶 (top) ,堆顶的键值为堆中所有元素的最大值(或最小值)。
一个堆要么是大顶堆、要么是小顶堆,二者只能取其一。堆上节点的键值不局限于实数,但是节点间的关系必须定义为某种全序关系。
堆也经常被称为 优先队列 (priority queue) ,例如在 C++ 语言的 STL 库中就有 priority_queue
的实现。
堆这一概念指的是一类抽象数据结构,并未规定其具体实现,只要一种数据结构满足堆属性,它就可以被称为堆。事实上,堆的实现方式有很多种,并且各有优缺点。
下图是几个不同实现的大顶堆的例子。
堆的重要之处在于,它可以提供快速地从大量元素中取出最值的功能,并且在插入元素或取出堆顶时能快速地维护整个堆,保证每个节点都满足堆属性。事实上,维护堆属性的目的就是保证能够一直快速地从堆顶处取出最值,这是堆的核心目的。这里的“快速”指的是 、 或其他低时间复杂度,取决于堆的具体实现。
一般来说,一个堆 至少 会提供以下基本功能:
插入操作:向堆中插入一个元素,并维持堆属性。
查询操作:获取堆顶元素,即获取堆中的最大值(或最小值)。注意通常只允许访问堆顶元素的键值。
弹出操作:将堆顶元素取出,并维持堆属性。注意通常只允许取出堆顶。
事实上,堆还有一些其他的基本功能,但是我认为初学者并不需要了解那么多(其实也很少用到),因此这里就不涉及了。
需要注意的是,堆中的元素并不像二叉查找树一样是有序的,而仅是部分有序的,在堆上进行中序遍历得到的并不是一个有序序列,千万不要弄错了。
# 常见堆实现的对比
这里记录了部分常见的堆的实现,以大顶堆为例,对它们的各类操作的性能进行对比,可以在此查阅。
注意,这里的时间复杂度有些是均摊的。
堆的实现 | 获取堆顶 | 弹出堆顶 | 插入元素 | 增大元素键值 | 合并 |
---|---|---|---|---|---|
二叉堆 | |||||
左偏树 | |||||
二项堆 | |||||
斐波那契堆 | |||||
配对堆 |
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01