堆-Heap

发表于 | 分类于
字数统计: 679

基本概念

堆是一种数据结构，定义为一棵完全二叉树。假如用数组储存堆结构，那么对于某个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} \times 1 + 2^{h-2} \times 2 + … + 2^{1} \times {h-1} + h$$

这是一个等比数列，通过将它乘以2，并做差，得到：
$$ 2^{h+1} - 2 - h $$
因为$h = logn$，所以heapify的时间复杂度为$O(n)$。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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 中的堆

在Java中，堆通过优先队列实现，即PriorityQueue。在初始化堆的时候，需要定义堆的大小和排序方式。默认为小根堆。

1
2
3
4
5
6
7
8
9
10
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