数据结构之优先队列和堆
什么是优先队列
我们都知道队列是一种先进先出、后进后出的数据结构,就如同日常生活中的排队一样,先到先得。而优先队列则是一种特殊的队列,优先队列与普通队列最大的不同点就在于出队顺序不一样。
因为优先队列的出队顺序与入队顺序无关,和优先级有关。也就是按元素的优先级决定其出队顺序,优先级高的先出队,优先级低的后出队,这也是为什么这种数据结构叫优先队列的原因。
这就好比现实生活中在银行排队办理业务,持有金卡的客户可以优先于普通卡的客户被接待,而钻石卡的客户又优先于金卡的客户,以此类推。这就是一种优先队列。
应用场景:
- 优先队列的应用场景非常多,比如,任务调度器、赫夫曼编码、图的最短路径、最小生成树算法等等。不仅如此,很多语言中,都提供了优先级队列的实现,比如,Java 的
PriorityQueue
,C++ 的priority_queue
等。
堆的基础表示
堆(Heap)简单来说是一种特殊的树,那么什么样的树才是堆呢?我罗列了两点要求,只要满足这两点,它就是一个堆:
- 堆是一个完全二叉树。完全二叉树:把元素顺序排列成树的形状
- 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值
第一点,堆必须是一个完全二叉树。还记得我们之前讲的完全二叉树的定义吗?完全二叉树要求,除了最后一层,其他层的节点个数都是满的,最后一层的节点都靠左排列。
第二点,堆中的每个节点的值必须大于等于(或者小于等于)其子树中每个节点的值。实际上,我们还可以换一种说法,堆中每个节点的值都大于等于(或者小于等于)其左右子节点的值。这两种表述是等价的。
对于每个节点的值都大于等于子树中每个节点值的堆,我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆,我们叫做“小顶堆”。
清楚了定义之后,我们来直观的看一下什么是堆:
在上图中,第 1 个和第 2 个是大顶堆,第 3 个是小顶堆,第 4 个不是堆。除此之外,从图中还可以看出来,对于同一组数据,我们可以构建多种不同形态的堆。
如何实现一个堆?
堆的实现并不局限于某一种特定的方式,可以使用链式树形结构(节点有左右指针)实现,也可以使用数组实现,因为完全二叉树的特性是一层一层按顺序排列的,完全可以紧凑地放在数组中。而且基于数组实现堆是一种比较巧妙且高效的方式,也是最常用的方式。
用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。如下图所示:
从图中我们可以看到节点的存放规律就是:数组中下标为 $i$ 的节点的左子节点,就是下标为 $2∗i$ 的节点,右子节点则是下标为 $2∗i+1$ 的节点。所以反过来,其父节点也就是下标为 $\frac{i}{2}$ 的节点。
parent(i) = i / 2left child(i) = 2 * iright child(i) = 2 * i + 1
通过这种方式,我们只要知道根节点存储的位置,这样就可以通过下标计算,把整棵树都串起来。一般情况下,为了方便计算子节点,根节点会存储在下标为 1 的位置。
如果从 0 开始存储,实际上处理思路是没有任何变化的,唯一变化的就是计算子节点和父节点的下标的公式改变了:如果节点的下标是 $i$,那左子节点的下标就是 $2∗i+1$,右子节点的下标就是 $2∗i+2$,父节点的下标就是 $\frac{i-1}{2}$。如下图所示:
有了以上的认知后,接下来,我们就可以先编写一个堆的基础框架代码了:
package heap;import java.util.ArrayList;import java.util.Collections;/** * 基于数组实现的最大堆 * 堆中的元素需要具有可比较性,所以需要实现Comparable * 在此实现中是从数组的下标0开始存储元素,因为使用ArrayList作为数组的角色 * * @author 01 * @date 2021-01-19 **/public class MaxHeap<E extends Comparable<E>> { /** * 使用ArrayList的目的是无需关注动态扩缩容逻辑 */ private final ArrayList<E> data; public MaxHeap(int capacity) { this.data = new ArrayList<>(capacity); } public MaxHeap() { this.data = new ArrayList<>(); } /** * 返回对中的元素个数 */ public int size() { return data.size(); } /** * 判断堆是否为空 */ public boolean isEmpty() { return data.isEmpty(); } /** * 根据传入的index,计算其父节点所在的下标 */ private int parent(int index) { if (index == 0) { throw new IllegalArgumentException("index-1 doesn't have parent."); } return (index - 1) / 2; } /** * 根据传入的index,计算其左子节点所在的下标 */ private int leftChild(int index) { return index * 2 + 1; } /** * 根据传入的index,计算其右子节点所在的下标 */ private int rightChild(int index) { return index * 2 + 2; }}
向堆中添加元素和Sift Up
往堆中添加一个元素后,我们需要继续满足堆的两个特性。如果我们把新添加的元素放到数组的最后,如下图,是不是就不符合堆的特性了?
于是,我们就需要进行调整,让其重新满足堆的特性,这个过程就叫做堆化(heapify)。堆化实际上有两种,从下往上(Sift Up)和从上往下(Sift Down)。这里我先讲从下往上的堆化方法。堆化非常简单,就是顺着节点所在的路径,向上或者向下,对比,然后交换。
看下面这张使用Sift Up方式的堆化过程分解图。我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系,我们就互换两个节点。一直重复这个过程,直到父子节点之间满足刚说的那种大小关系:
将这个流程翻译成具体的实现代码如下:
/** * 向堆中添加元素 e */public void add(E e) { data.add(e); siftUp(data.size() - 1);}/** * 从下往上调整元素的位置,直到元素到达根节点或小于父节点 */private void siftUp(int k) { while (k > 1 && isParentLessThan(k)) { // 交换 k 与其父节点的位置 Collections.swap(data, k, parent(k)); k = parent(k); }}/** * 判断 k 的父节点是否小于 k */private boolean isParentLessThan(int k) { return data.get(parent(k)).compareTo(data.get(k)) < 0;}
从堆中取出元素和Sift Down
从堆的定义的第二条中,任何节点的值都大于等于(或小于等于)子树节点的值,我们可以发现,堆顶元素存储的就是堆中数据的最大值或者最小值。
而从堆中取出元素其实就是取出堆中最大或最小的元素,并且取出后会删除,所以也可以理解为删除堆顶元素。堆顶也就是堆的根节点,或者说是数组下标为0或1的元素。
假设我们构造的是大顶堆,堆顶元素就是最大的元素。当我们删除堆顶元素之后,就需要把最后一个节点放到堆顶,然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的,互换两个节点,并且重复进行这个过程,直到父子节点之间满足大小关系为止。这就是从上往下(Sift Down)的堆化方法。如下图:
因为我们移除的是数组中的最后一个元素,而在堆化的过程中,都是交换操作,不会出现数组中的“空洞”,所以这种方法堆化之后的结果,肯定满足完全二叉树的特性。
具体的实现代码如下:
/** * 获取堆顶元素 */public E findMax() { if (isEmpty()) { throw new IllegalArgumentException("Can't find max when heap is empty."); } return data.get(0);}/** * 从堆中取出元素,也就是取出堆顶元素 */public E extractMax() { E ret = findMax(); // 交换根节点与最后一个节点的位置 Collections.swap(data, 0, data.size() - 1); // 删除最后一个节点 data.remove(data.size() - 1); siftDown(0); return ret;}/** * 从上往下调整元素的位置,直到元素到达叶子节点或大于左右子节点 */private void siftDown(int k) { // 左子节点大于size时就证明到底了 while (leftChild(k) < data.size()) { int leftChildIndex = leftChild(k); int rightChildIndex = leftChildIndex + 1; int maxChildIndex = leftChildIndex; // 左右子节点中最大的节点下标 if (rightChildIndex < data.size() && isGreaterThan(rightChildIndex, leftChildIndex)) { maxChildIndex = rightChildIndex; } // 大于最大的子节点证明 k 已经大于左右子节点,无需再继续下沉了 if (data.get(k).compareTo(data.get(maxChildIndex)) >= 0) { break; } // 否则,交换 k 与其最大子节点的位置,继续下沉 Collections.swap(data, k, maxChildIndex); k = maxChildIndex; }}/** * 判断右子节点是否大于左子节点 */private boolean isGreaterThan(int rightChildIndex, int leftChildIndex) { return data.get(rightChildIndex).compareTo(data.get(leftChildIndex)) > 0;}
到此为止,我们就已经实现了堆的核心操作。接下来我们使用一个简单的测试用例,测试下这个堆的行为是否符合预期。测试代码如下:
/** * 测试堆的行为是否符合预期 */private static void testAddAndExtractMax() { int n = 1000000; // 随机往堆里添加n个元素 MaxHeap<Integer> maxHeap = new MaxHeap<>(); Random random = new Random(); for (int i = 0; i < n; i++) { maxHeap.add(random.nextInt(Integer.MAX_VALUE)); } // 取出堆中的所有元素,放到arr中 int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = maxHeap.extractMax(); } // 由于堆的特性,此时arr中的元素理应是有序的 // 所以这里校验一下arr是否是有序的,如果无序则代表堆的实现有问题 for (int i = 1; i < n; i++) { if (arr[i - 1] < arr[i]) { throw new IllegalArgumentException("Error"); } } System.out.println("Test MaxHeap completed.");}public static void main(String[] args) { testAddAndExtractMax();}
Heapify 和 Replace
堆的 Heapify 和 Replace 也是比较常见的操作,虽然使用之前所编写的代码也能实现,但并不是那么好使,例如实现 Replace 需要两次$O(logn)$的操作。所以在本小节就为这两个操作,单独编写相应的代码。
Replace
- Replace:取出最大元素后,放入一个新元素
- 使用已有代码的实现:可以先
extractMax
,再add
,两次$O(logn)$的操作 - 新的实现:可以直接将堆顶元素替换以后进行Sift Down,只需要一次$O(logn)$的操作
有了之前的代码基础,实现 Replace 就非常简单了,只需要几行代码。如下:
/** * 取出堆中的最大元素,并且替换成元素e */public E replace(E e) { E ret = findMax(); // 替换堆顶元素 data.set(0, e); siftDown(0); return ret;}
Heapify
- Heapify:将任意数组整理成堆的形状,也就是对一个数组进行堆化,或者说是建堆
- 使用已有代码的实现:遍历数组,调用
add
将每个元素添加到堆里。时间复杂度是$O(nlogn)$ - 新的实现:从后往前处理数组,并且每个数据都是从上往下堆化。因为叶子节点往下堆化只能自己跟自己比较,所以我们直接从最后一个非叶子节点开始,依次堆化就行了。这样相当于只需要对数组中一半的元素进行Sift Down操作。时间复杂度是$O(n)$
建堆分解步骤图如下:
同样,基于之前已有的代码,Heapify 实现起来也非常的简单,我们可以选择在构造器中提供这个功能。具体的实现代码如下:
public MaxHeap(E[] arr) { this.data = asArrayList(arr); // 最后一个非叶子节点的下标 int lastNode = parent(data.size() - 1); for (int i = lastNode; i >= 0; i--) { // 从后往前依次堆化 siftDown(i); }}/** * 将数组转换为ArrayList */private ArrayList<E> asArrayList(E[] arr) { ArrayList<E> ret = new ArrayList<>(); Collections.addAll(ret, arr); return ret;}
基于堆的优先队列
现在我们已经了解了优先队列和堆,并且自己动手实现了一个堆,因此,不难看得出来,堆和优先队列非常相似。一个堆其实就可以看作是一个优先队列。Java中的优先队列也是基于堆实现的,是一个小顶堆。
很多时候,它们只是概念上的区分而已。往优先队列中插入一个元素,就相当于往堆中插入一个元素;从优先队列中取出优先级最高的元素,就相当于取出堆顶元素。所以,堆和优先队列在基本行为上是等价的。
我们之前也提到了优先队列可以使用不同的方式进行实现,但使用堆这种数据结构来实现优先队列是最高效也最符合直觉的,因为堆本身就是一个优先队列。
从下图中可以看到使用不同数据结构实现优先队列的时间复杂度:
接下来,我们就实现一个基于堆的优先队列。首先,定义一个队列接口:
package queue;/** * 队列数据结构接口 * * @author 01 **/public interface Queue<E> { /** * 新元素入队 * * @param e 新元素 */ void enqueue(E e); /** * 元素出队 * * @return 元素 */ E dequeue(); /** * 获取位于队首的元素 * * @return 队首的元素 */ E getFront(); /** * 获取队列中的元素个数 * * @return 元素个数 */ int getSize(); /** * 队列是否为空 * * @return 为空返回true,否则返回false */ boolean isEmpty();}
然后实现接口中的方法,由于我们之前已经实现了一个堆,所以这个优先队列实现起来就非常简单了:
package queue;import heap.MaxHeap;/** * 基于堆实现的优先队列 * * @author 01 * @date 2021-01-19 */public class PriorityQueue<E extends Comparable<E>> implements Queue<E> { private final MaxHeap<E> maxHeap; public PriorityQueue() { maxHeap = new MaxHeap<>(); } @Override public int getSize() { return maxHeap.size(); } @Override public boolean isEmpty() { return maxHeap.isEmpty(); } @Override public E getFront() { return maxHeap.findMax(); } @Override public void enqueue(E e) { maxHeap.add(e); } @Override public E dequeue() { return maxHeap.extractMax(); }}
©著作权归作者所有:来自51CTO博客作者ZeroOne01的原创作品,如需转载,请注明出处,否则将追究法律责任每一份赞赏源于懂得
赞赏
0人进行了赞赏支持
更多相关文章
- Web UI自动化测试之元素定位
- LeetCode #27 移除元素
- (美团)巧用数组下标,轻轻松松找出所有元素
- LeetCode 图解 | 237.删除链表中的节点
- 超详细!详解一道高频算法题:数组中的第 K 个最大元素
- 动画:面试必刷之二叉树搜索第 K 大节点
- 动画:面试必刷之二维数组中查找一个元素
- 前 K 个高频元素告诉你桶排序有啥用
- SSH AKS集群节点的几种方法(一)