力扣labuladong——一刷day94

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

二叉堆（Binary Heap）没什么神秘，性质比二叉搜索树 BST 还简单。其主要操作就两个，sink（下沉）和 swim（上浮），用以维护二叉堆的性质。其主要应用有两个，首先是一种排序方法「堆排序」，第二是一种很有用的数据结构「优先级队列」

一、二叉堆

public class MaxPQ<Key extends Comparable<Key>> {// 存储元素的数组private Key[] pq;// 当前 Priority Queue 中的元素个数private int size = 0;public MaxPQ(int cap) {// 索引 0 不用，所以多分配一个空间pq = (Key[]) new Comparable[cap + 1];}/* 返回当前队列中最大元素 */public Key max() {return pq[1];}/* 插入元素 e */public void insert(Key e) {...}/* 删除并返回当前队列中最大元素 */public Key delMax() {...}/* 上浮第 x 个元素，以维护最大堆性质 */private void swim(int x) {...}/* 下沉第 x 个元素，以维护最大堆性质 */private void sink(int x) {...}/* 交换数组的两个元素 */private void swap(int i, int j) {Key temp = pq[i];pq[i] = pq[j];pq[j] = temp;}/* pq[i] 是否比 pq[j] 小？ */private boolean less(int i, int j) {return pq[i].compareTo(pq[j]) < 0;}/* 还有 left, right, parent 三个方法 */public class MaxPQ <Key extends Comparable<Key>> {// 为了节约篇幅，省略上文给出的代码部分...private void swim(int x) {// 如果浮到堆顶，就不能再上浮了while (x > 1 && less(parent(x), x)) {// 如果第 x 个元素比上层大// 将 x 换上去swap(parent(x), x);x = parent(x);}}public class MaxPQ <Key extends Comparable<Key>> {// 为了节约篇幅，省略上文给出的代码部分...private void sink(int x) {// 如果沉到堆底，就沉不下去了while (left(x) <= size) {// 先假设左边节点较大int max = left(x);// 如果右边节点存在，比一下大小if (right(x) <= size && less(max, right(x)))max = right(x);// 结点 x 比俩孩子都大，就不必下沉了if (less(max, x)) break;// 否则，不符合最大堆的结构，下沉 x 结点swap(x, max);x = max;}}public class MaxPQ <Key extends Comparable<Key>> {// 为了节约篇幅，省略上文给出的代码部分...public void insert(Key e) {size++;// 先把新元素加到最后pq[size] = e;// 然后让它上浮到正确的位置swim(size);}public class MaxPQ <Key extends Comparable<Key>> {// 为了节约篇幅，省略上文给出的代码部分...public Key delMax() {// 最大堆的堆顶就是最大元素Key max = pq[1];// 把这个最大元素换到最后，删除之swap(1, size);pq[size] = null;size--;// 让 pq[1] 下沉到正确位置sink(1);return max;}
}}}}}