Heap 堆

Heap 本质是一个用Array实现的完全二叉树，这个树的root节点代表整个Heap里的最大（max heap）或最小值（min heap）

常用 API

• peek() -->查看堆顶元素O(1)
• poll() --> 拿出堆顶元素 O(logN)
• offer() --> 添加元素 O(logN)

Online vs Offline 算法

Online 算法（用堆）：针对一组流数据，没有固定长度，可以随时根据需求scalable
Offline 算法（Sorting）：针对一组固定长度数据，每次scale后要重新计算

Top K问题

这类问题一般用堆解决

class LeetCode215 {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};

        System.out.println(new Solution().findKthLargest(nums, 3));
    }

    static class Solution {
        public int findKthLargest(int[] nums, int k) {
            int heapSize = nums.length;
            buildMaxHeap(nums, heapSize);
            for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
                swap(nums, 0, i);
                --heapSize;
                maxHeapify(nums, 0, heapSize);
            }
            return nums[0];
        }

        public void buildMaxHeap(int[] a, int heapSize) {
            for (int i = heapSize / 2; i >= 0; --i) {
                maxHeapify(a, i, heapSize);
            }
        }

        public void maxHeapify(int[] a, int i, int heapSize) {
            int l = i * 2 + 1, r = i * 2 + 2, largest = i;
            if (l < heapSize && a[l] > a[largest]) {
                largest = l;
            }
            if (r < heapSize && a[r] > a[largest]) {
                largest = r;
            }
            if (largest != i) {
                swap(a, i, largest);
                maxHeapify(a, largest, heapSize);
            }
        }

        public void swap(int[] a, int i, int j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}