排序算法入门（四）：堆排序 —— 用完全二叉树原地排序

public class HeapSort {

    public static void sort(int[] a) {
        if (a == null || a.length < 2) {
            return;                 // 0 或 1 个元素已经有序，也避免后面下标越界
        }
        buildHeap(a);
        // 每轮把堆顶（当前最大值）换到有效区间末尾，之后它永久归位
        for (int end = a.length - 1; end > 0; end--) {
            swap(a, 0, end);
            // end 已归位，堆的有效范围缩到 [0, end)，此时只有根被破坏
            siftDown(a, 0, end);
        }
    }

    private static void buildHeap(int[] a) {
        // 下标 >= n/2 的结点全是叶子，本身就是合法的堆，不用处理
        // 从最后一个非叶结点倒着走，保证下沉时左右子树已经是堆
        for (int i = a.length / 2 - 1; i >= 0; i--) {
            siftDown(a, i, a.length);
        }
    }

    /** 让 a[i] 在 [0, size) 这个范围内下沉到合适位置 */
    private static void siftDown(int[] a, int i, int size) {
        while (true) {
            int left = 2 * i + 1;
            if (left >= size) {
                return;                     // 没有孩子，已经落到叶子
            }
            int larger = left;
            int right = left + 1;
            if (right < size && a[right] > a[left]) {
                larger = right;             // 先选出较大的孩子，它才有资格和父结点竞争
            }
            if (a[i] >= a[larger]) {
                return;                     // 父结点不小于较大的孩子，堆性质已满足，可以停
            }
            swap(a, i, larger);
            i = larger;                     // 继续从被换下去的位置往下检查
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        int[] data = {4, 1, 7, 3, 9, 2, 8, 0, 5, 6};
        sort(data);
        System.out.println(java.util.Arrays.toString(data));
        // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}

PriorityQueue<Integer> minHeap = new PriorityQueue<>();                     // 默认小顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

minHeap.offer(5);
minHeap.offer(1);
minHeap.peek();      // 1，O(1)：堆顶就是全局最小值
minHeap.poll();      // 1，O(log n)：弹出后自动修复堆

ScheduledExecutorService pool = Executors.newScheduledThreadPool(2);
// 堆顶即最近到期的任务
pool.schedule(() -> System.out.println("run"), 3, TimeUnit.SECONDS);

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

static ListNode mergeKLists(ListNode[] lists) {
    // 堆里只放每条链表"当前最小的那个候选"，保证堆顶是全局最小
    PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode head : lists) {
        if (head != null) {
            pq.offer(head);            // 空链表不进堆，否则后面取 val 会 NPE
        }
    }
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        tail.next = node;              // 直接接上已有结点，不新建对象
        tail = node;
        if (node.next != null) {
            pq.offer(node.next);       // 该链表的下一个元素成为新候选
        }
    }
    return dummy.next;
}

import java.util.Arrays;
import java.util.PriorityQueue;

public class TopK {

    /** 返回数组中最大的 k 个数，结果不保证有序 */
    public static int[] topK(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        k = Math.min(k, nums.length);

        // 求最大的 k 个用小顶堆：堆顶是这 k 个里最小的，充当"守门员"
        // 新元素只有比堆顶大才值得进来，进来就要挤掉堆顶
        PriorityQueue<Integer> heap = new PriorityQueue<>(k);
        for (int v : nums) {
            if (heap.size() < k) {
                heap.offer(v);              // 还没装满，先无条件收下
            } else if (v > heap.peek()) {
                heap.poll();                // 堆顶不够格，淘汰它
                heap.offer(v);
            }
        }

        int[] res = new int[heap.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = heap.poll();           // 小顶堆依次弹出，结果是升序
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        System.out.println(Arrays.toString(topK(nums, 2)));   // [5, 6]
    }
}