堆理论基础
# 什么是堆(优先级队列)
堆(也称为优先级队列)是一种特殊的树形数据结构。
根据根节点的值与子节点的值的大小关系,堆又分为最大堆和最小堆。
- 在最大堆中,每个节点的值总是大于或等于其任意子节点的值,因此最大堆的根节点就是整个堆的最大值。
- 在最小堆中,每个节点的值总是小于或等于其任意子节点的值,因此最小堆的根节点就是整个堆的最小值
例如,图(a)所示是一个最大堆,图(b)所示是一个最小堆。
堆通常用完全二叉树实现。在完全二叉树中,除最低层之外,其他层都被节点填满,最低层尽可能从左到右插入节点。上图中的两个堆都是完全二叉树。
完全二叉树又可以用数组实现,因此堆也可以用数组实现。如果从堆的根节点开始从上到下按层遍历,并且每层从左到右将每个节点按照 0、1、2 等的顺序编号,将编号为 0 的节点放入数组中下标为 0 的位置,编号为1的节点放入数组中下标为1的位置,以此类推就可以将堆的所有节点都添加到数组中。上图(a)中的堆可以用数组表示成下图(a)所示的形式,而上图(b)中的堆可以用数组表示成下图(b)所示的形式。
⭐ 如果数组中的一个元素的下标为 i,那么它在堆中对应节点的父节点在数组中的下标为 (i - 1) / 2
,而它的左右子节点在数组中的下标分别为 2 * i + 1
和 2 * i + 2
。
# 在堆中添加元素
为了在最大堆中添加新的节点,有以下三个步骤:
- 先从上到下、从左到右找出第 1 个空缺的位置,并将新节点添加到该空缺位置
- 如果新节点的值比它的父节点的值大,那么交换它和它的父节点
- 重复这个交换过程,直到新节点的值小于或等于它的父节点,或者它已经到达堆的顶部位置。
在最小堆中添加新节点的过程与此类似,唯一的不同是要确保新节点的值要大于或等于它的父节点。
所以,堆的添加操作是一个自下而上的操作。
举个例子,如果上图(a)的最大堆中添加一个新的元素 95:
- 由于节点 60 的右子节点是第1个空缺的位置,因此创建一个新的节点95并使之成为节点60的右子节点
- 此时新节点95的值大于它的父节点60的值,这违背了最大堆的定义,于是交换它和它的父节点
- 由于新节点95的值仍然大于它的父节点90的值,因此再交换新节点95和它的父节点90。此时堆已经满足最大堆的定义。
整体过程如下图:
堆的插入操作可能需要交换节点,以便把节点放到合适的位置,交换的次数最多为二叉树的深度,因此如果堆中有 n 个节点,那么它的插入操作的时间复杂度是 O(logn)
。
# 在堆中删除元素
通常只删除位于堆顶部的元素。
以删除最大堆的顶部节点为例:
- 将堆最低层最右边的节点移到堆的顶部
- 如果此时它的左子节点或右子节点的值大于它,那么它和左右子节点中值较大的节点交换
- 如果交换之后节点的值仍然小于它的子节点的值,则再次交换,直到该节点的值大于或等于它的左右子节点的值,或者到达最低层为止
删除最小堆的顶部节点的过程与此类似,唯一的不同是要确保节点的值要小于它的左右子节点的值。
所以,堆的删除操作是一个自上而下的操作。
举个例子,删除上图(a)中最大堆的顶部元素之后:
- 将位于最低层最右边的节点60移到最大堆的顶部,如下图(c)所示
- 此时节点60比它的左子节点80和右子节点90的值都小,因此将它和值较大的右子节点90交换,交换之后的堆如图(d)所示
- 此时节点60大于它的左子节点30,满足最大堆的定义
堆的删除操作可能需要交换节点,以便把节点放到合适的位置,交换的次数最多为二叉树的深度,因此如果堆中有 n 个节点,那么它的删除操作的时间复杂度是 O(logn)
。
# Java 提供的堆实现
Java提供了类型 PriorityQueue
实现数据结构堆。
PriorityQueue在默认情况下是一个最小堆,如果使用最大堆调用构造函数就需要传入 Comparator
改变比较排序的规则。
// 构造小顶堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o1 - o2);
// 构造大顶堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
PriorityQueue
实现了接口 Queue
,它常用的函数如表所示
这就是为啥堆被称为优先级队列的原因
PriorityQueue 和其他实现接口Queue的类型一样,在某些时候调用函数add、remove和element时可能会抛出异常,但调用函数offer、poll和peek不会抛出异常。例如,如果调用函数remove从一个空堆中删除堆顶元素,就会抛出异常。但如果调用函数poll从一个空堆中删除堆顶元素,则会返回null。
⭐ 值得强调的是,虽然Java中的PriorityQueue实现了Queue接口,但它并不是一个队列,也不是按照“先入先出”的顺序删除元素的。
PriorityQueue是一个堆,每次调用函数remove或poll都将删除位于堆顶的元素。
PriorityQueue的删除顺序与元素添加的顺序无关。
同理,PriorityQueue的函数element和peek都返回位于堆顶的元素,即根据堆的类型返回值最大或最小的元素,这与元素添加的顺序无关。
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~