二叉堆

参考这个https://meowrain.cn/archives/dui-pai-xu
堆（Heap）是一类数据结构，它们拥有树状结构，且能够保证父节点比子节点大（或小）。当根节点保存堆中最大值时，称为大根堆；反之，则称为小根堆。
二叉堆（Binary Heap）是最简单、常用的堆，是一棵符合堆的性质的完全二叉树。它可以实现$O(logn)$地插入或删除某个值，并且$O(1)$ 地查询最大（或最小）值。
其主要操作有两个，sink（下沉）和 swim（上浮）
主要应用有两个，堆排序，优先级队列

二叉堆还分为最大堆和最小堆。
最大堆的性质是：每个节点都大于等于它的两个子节点。
最小堆的性质是：每个节点都小于等于它的子节点。

public class MaxPQ<Key extends Comparable<Key>> {
    //存储元素得数组
    private Key[] pq;
    //当前优先队列中得元素个数
    private int size = 0;

    public MaxPQ(int cap) {
        //索引0不用，所以多分配一个空间
        pq = (Key[]) new Comparable[cap + 1];
    }

    /* 返回当前队列中的最大元素*/
    public Key max() {
        return pq[1];
    }

    private void swim(int x) {
        // 如果浮到堆顶，就不能再上浮了
        while (x > 1 && less(parent(x), x)) { //如果父亲更小且上浮的元素下标大于1
            //如果第x个元素比上层大
            //把x换上去
            swap(parent(x), x);
            x = parent(x);
        }
    }

    private void sink(int x) {
        //如果沉到堆的底部，就沉不下去了
        while (left(x) <= size) {
            //假设左边节点比较大
            int max = left(x);
            //如果右边节点存在，比较一下大小
            if (right(x) <= size && less(left(x), right(x))) {
                max = right(x);
            }
            //节点x比两个孩子都大,就不用下沉了
            if (less(max, x)) break;
            x = max;
        }
    }

    /*插入元素*/
    public void insert(Key element) {
        size++;
        //先加加，因为不用0号索引
        pq[size] = element;
        // 然后让它上浮到正确位置
        swim(size);
    }

    /*删除并且返回当前队列中的最大元素*/
    public Key delMax() {
        // 最大堆的堆顶就是最大元素
        Key max = pq[1];
        // 把这个最大元素换到最后，删除之
        swap(1, size);
        pq[size] = null; //置空
        size--;
        // 让 pq[1] 下沉到正确位置
        sink(1);
        return max;
    }

    /*交换数组的两个元素*/
    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;
    }

    private int left(int x) {
        return 2 * x + 1;
    }

    private int right(int x) {
        return 2 * x + 2;
    }

    private int parent(int x) {
        return (x - 1) / 2;
    }
}

例题：
合并 k 个有序链表
https://leetcode.cn/problems/merge-k-sorted-lists/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
          if(lists.length == 0) return null;
        //虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        //优先队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b)->(a.val - b.val));
        //把k个链表的头节点加入最小堆
        for(ListNode head : lists) {
            if(head != null) {
                pq.add(head);
            }
        }

        while(!pq.isEmpty()){
            //获取最小节点，接到结果链表中
            ListNode node = pq.poll(); //获取并删除堆顶元素(也就是最大优先级元素)
            p.next = node;
            if(node.next != null){
                pq.add(node.next);
            }
            //p指针不断前进
            p = p.next;
        }
        return dummy.next;
    }
}