基本概念

堆是一种数据结构，定义为一棵完全二叉树。假如用数组储存堆结构，那么对于某个index为i的节点来说，它的左儿子的index为2*i+1，右儿子为2*i+2。
堆有两种，小根堆和大根堆。对于小根堆，它的每个节点的值都小于该节点左右儿子的值。同理大根堆。

堆的操作

堆化(heapify)
O(n)
表面上看heapify应该为 $O(nlogn)$ ，但是对于在第 $h-i$ 层的节点来说，它最多的shiftdown深度为 $i$ ，shiftdown每一层的复杂度为 $O(1)$ ，而第 $h - i$ 层一共有 $2 ^ {h - i}$ 个节点，所以整个heapify的时间复杂度为：
$2^{h - 1} *1 + 2^{h - 2} *2 +...+ 2^{1} *(h - 1) + h$
这是一个等比数列，通过将它乘以2，并做差，得到：
$2^{h+1} - 2 - h$
因为 $h = logn$ ，所以heapify的时间复杂度为 $O(n)$ 。

public class Heap {
    
    public void heapify(int[] A) {
        for (int i = (A.length - 2) / 2; i >= 0; i--) {
            shiftdown(A, i);
        }
    }
    
    public void shiftdown(int[] A, int k) {
        int n = A.length;
        int minIndex = k;
        int left = 2 * k + 1;
        int right = 2 * k + 2;
        if (left < n && A[left] < A[minIndex]) {
            minIndex = left;
        }
        if (right < n && A[right] < A[minIndex]) {
            minIndex = right;
        }
        if (minIndex != k) {
            int tmp = A[k];
            A[k] = A[minIndex];
            A[minIndex] = tmp;
            shiftdown(A, minIndex);
        }
    }
}

添加
O(logn)
删除
O(logn)
返回堆顶
O(1)

public class minHeap {
    
    int[] A;
    int size;
    int maxSize;
    
    public minHeap(int n) {
        A = new int[n];
        size = 0;
        maxSize = n;
    }
    
    public void add(int x) {
        if (size == A.length) {
            return;
        }
        A[size] = x;
        shiftup(size);
        size++;
    }
    
    public int poll() {
        if (size == 0) {
            return Integer.MIN_VALUE;
        }
        size--;
        swap(0, size);
        shiftdown(0);
        return A[size];
    }
    
    public int peek() {
        if (size == 0) {
            return Integer.MIN_VALUE;
        }
        return A[0];
    }
    
    private void shiftdown(int k) {
        int minIndex = k;
        int left = 2 * k + 1;
        int right = 2 * k + 2;
        if (left < size && A[left] < A[minIndex]) {
            minIndex = left;
        }
        if (right < size && A[right] < A[minIndex]) {
            minIndex = right;
        }
        if (minIndex != k) {
            swap(minIndex, k);
            shiftdown(A, minIndex);
        }
    }
    
    private void shiftup(int k) {
        int parent = k / 2;
        if (A[k] < A[parent]) {
            swap[k, parent];
            shiftup(parent);
        }
    }
    
    private void swap(int a, int b) {
        int tmp = A[a];
        A[a] = A[b];
        A[b] = tmp;
    }
}

Java 内置PriorityQueue

PriorityQueue<Integer> heap = new PriorityQueue<>(size, new Comparator<Integer>() {
        @Override
        public int compare {
                return a - b; // 小根堆 
                return b - a; // 大根堆
        }
});
heap.offer(); // 添加
heap.poll(); // 删除
heap.peek(); // 返回堆顶元素，即最小或最大值