Skip to main content

Heap 堆

定义​

Heap 本质是一个用 Array 实现的 Complete Binary Tree, 这个 Tree 的 root 节点代表整个 Heap 里的最大(max heap) 或者最小值(min heap)。

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

常用方法 (Common APIs)​

  • peek(): 查看堆顶元素 O(1)
  • poll(): 拿到堆顶元素 O(logN)
  • offer(): 添加元素 O(logN)
  • size(): 堆中元素总数
  • isEmpty(): 判断是否为空

Online vs Offline Algorithm​

  • Online Algorithm (using Heap): 针对一组流数据，没有固定长度，可以随时根据需求 scalable
  • Offline Algorithm (using Sorting): 针对一组固定长度数据，每次 scale 后要重新计算

Top K 问题 常见解题方式​

  • Sorting O(nlogn): Sort the array and get the kth element
  • Max Heap O(n + klogn): Heapify the array, then poll k times
  • Min Heap O(nlogk)
    • Maintain a size k min heap
    • Add element to min heap if greater than or equal to top element, adjust size if necessary
    • At the end top of heap is the kth largest

Q215 例题: Kth Largest Element in an Array (Top K 问题)​

High Level Idea​

online Algorithm

  1. Initialize a min heanp
  2. For each element x in the array
    • offer to heap if heap size < k or x >= top of heap
    • Adjust heap size if necessary
  3. Return the top of heap

代码​

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

    for (int x : nums) {
        if (minHeap.size() < k || x >= minHeap.peek()) {
            minHeap.offer(x);
        }
        if (minHeap.size() > k) {
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

Q23 例题: Merge K Sorted Lists​

对于一个固定数量​

简单解题方法: 使用 K 个指针，谁小移动谁。

找出最小值​

现在有 k 个指针，每次添加并移动最小的指针,如何每次找到最小值:

  • Liniear Scan O(k)
  • Simple Sorting O(klogk)
  • Min Heap O(logk)

High Level Idea​

时间复杂度 O(nlogk), n = 所有 node 总数

online Algorithm

  1. Initialize min heap with all List head references
  2. While heap is not empty
    • Poll out top of heap (smallest pointer)
    • Add it to result list
    • Add its next node if there exists

代码​

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

    for (ListNode list: lists) {
        if (list != null) {
            minHeap.offer(list);
        }
    }
    ListNode res = new LisNode(0), cur = res; // Dummy head tech for linked list
    while (!minHeap.isEmpty()) {
        ListNode top = minHeap.poll();
        cur.next = top;
        cur = cur.next;
        if(top.next != null) {
            minHeap.offer(top.next);
        }
    }

    return res.next;
}

更多例题​

  • Top K Frequent Elements (347)
  • Meeting Rooms II (253)
  • Find Median From Data Stream (295)
  • Reorganize String (767)
  • Kth Largest Element in a Stream (703)

来源​