基本概念

堆是一種數(shù)據(jù)結構，定義為一棵完全二叉樹。假如用數(shù)組儲存堆結構，那么對于某個index為i的節(jié)點來說，它的左兒子的index為2*i+1，右兒子為2*i+2。
堆有兩種，小根堆和大根堆。對于小根堆，它的每個節(jié)點的值都小于該節(jié)點左右兒子的值。同理大根堆。

堆的操作

• 堆化(heapify)
  O(n)
  表面上看heapify應該為，但是對于在第層的節(jié)點來說，它最多的shiftdown深度為，shiftdown每一層的復雜度為，而第層一共有個節(jié)點， 所以整個heapify的時間復雜度為：
  
  這是一個等比數(shù)列，通過將它乘以2，并做差，得到：
  
  因為，所以heapify的時間復雜度為。

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 內(nèi)置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(); // 返回堆頂元素，即最小或最大值

Lintcode 相關練習

Top k Largest Numbers II
K Closest Points