堆

堆基础

堆的特点？

答案：

• 完全二叉树
• 大顶堆：父节点≥子节点
• 小顶堆：父节点≤子节点
• 插入、删除O(log n)
• 查找最值O(1)

Java中的堆

// 小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

minHeap.offer(3);
minHeap.offer(1);
minHeap.offer(2);
int min = minHeap.poll();  // 1

堆的应用

数组中的第K个最大元素（LeetCode 215）

答案：

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    return minHeap.peek();
}

前K个高频元素（LeetCode 347）

答案：

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    PriorityQueue<Integer> heap = new PriorityQueue<>(
        (a, b) -> map.get(a) - map.get(b)
    );

    for (int num : map.keySet()) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }

    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = heap.poll();
    }
    return result;
}

合并K个升序链表（LeetCode 23）

答案：

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>(
        (a, b) -> a.val - b.val
    );

    for (ListNode list : lists) {
        if (list != null) {
            heap.offer(list);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        curr.next = node;
        curr = curr.next;

        if (node.next != null) {
            heap.offer(node.next);
        }
    }
    return dummy.next;
}

数据流的中位数（LeetCode 295）

答案：

class MedianFinder {
    private PriorityQueue<Integer> maxHeap;  // 存较小的一半
    private PriorityQueue<Integer> minHeap;  // 存较大的一半

    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }

        // 平衡两个堆
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
        return maxHeap.peek();
    }
}

练习题

1. 最后一块石头的重量（LeetCode 1046）
2. 丑数II（LeetCode 264）
3. 滑动窗口中位数（LeetCode 480）
4. 查找和最小的K对数字（LeetCode 373）
5. IPO（LeetCode 502）