堆 - Heap

基本概念

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

堆的操作

• 堆化(heapify)
  O(n)
  表面上看heapify应该为，但是对于在第层的节点来说，它最多的shiftdown深度为，shiftdown每一层的复杂度为，而第层一共有个节点， 所以整个heapify的时间复杂度为：
  
  这是一个等比数列，通过将它乘以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 内置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