This page looks best with JavaScript enabled

小根堆-大根堆

 ·  ☕ 3 min read

理解堆的定义, 使用堆实现一个优先级队列, 查看 java.util.Timer 中的小根堆实现

堆的定义

堆是具有下面性质的完全二叉树:

  • 每个结点的值都小于或等于其左右孩子结点的值: 小根堆
  • 每个结点的值都大于或等于其左右孩子结点的值: 大根堆

用堆来实现优先级队列的话, 入队和出队操作的时间复杂度均为 O($log_{2}n$). 因为可以根据完全二叉树的性质设计入队和出队算法。

完全二叉树中, 结点从 1 开始按照层序编号, 若一个结点的编号为 i, 则它的双亲结点编号为 i/2, 左孩子是 2i,右孩子是 2i+1.

堆常用数组实现, 数组的下标表示完全二叉树中结点的编号.

存储结构
大根堆 大根堆添加元素过程

java.util.Timer

java.util.Timer 中的优先级队列实现就是使用的小根堆实现:

入队

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void add(TimerTask task) {
    // Grow backing store if necessary
    if (size + 1 == queue.length)
        queue = Arrays.copyOf(queue, 2*queue.length);
    
    // 将新提交的 task 放到堆的尾部
    queue[++size] = task;
    // 然后进行向上层的遍历
    fixUp(size);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

private void fixUp(int k) {
    // 保证编号 1 的结点是整个堆的最小值
    while (k > 1) {
        int j = k >> 1; // k >> 1 就是它的双亲结点在数组中的下标
        // 比较 k 和它的双亲结点
        if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime)
            // 如果 k 的值较大, 则储存在当前位置
            break;
        // 如果 k 的值较小, 则将它与双亲结点交换
        TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
        k = j;
    }
}

出队

1
2
3

TimerTask getMin() {
    return queue[1]; // 根结点即是堆中的最小值
}

1
2
3
4
5

void removeMin() {
    queue[1] = queue[size]; // 将最后一个结点值赋给根结点
    queue[size--] = null;  // Drop extra reference to prevent memory leak
    fixDown(1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

private void fixDown(int k) {
    int j;
    while ((j = k << 1) <= size && j > 0) {
        // j = k*2: 即 k 的左孩子结点
        // 左孩子与与右孩子比较
        if (j < size && queue[j].nextExecutionTime > queue[j+1].nextExecutionTime)
            // 如果左孩子较大, 则 j++
            j++; // j indexes smallest kid
        // 依据上面是否执行 j++, 与左孩子或右孩子比较
        if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime)
            break;
        // 如果孩子中存在大于k结点的, 则交换
        TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
        k = j;
    }
}

大小根堆

一个自己实现的支持大或小根堆的实现
https://github.com/stefanJi/Algorithm/blob/master/src/site/jiyang/DataStructure/Heap.java

  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
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

/**
 * Create by StefanJi in 2019-10-25
 */
public class Heap<T extends Comparable> {
    private static final int DEFAULT_SIZE = 16;
    public static final byte MAX_HEAP = 0;
    public static final byte MIN_HEAP = 1;

    @Retention(RetentionPolicy.SOURCE)
    @ByteDef({MAX_HEAP, MIN_HEAP})
    @Target({ElementType.FIELD, ElementType.PARAMETER})
    @interface Order { }

    private int count;
    private byte order;

    private Object[] tree;

    public Heap(@Order byte order) {
        this.order = order;
        tree = new Object[DEFAULT_SIZE];
    }

    public Heap(@Order byte order, int initCapacity) {
        this.order = order;
        if (initCapacity < 0) {
            throw new IllegalArgumentException("Illegal capacity: " + initCapacity);
        }
        if (initCapacity == 1) {
            initCapacity = 2;
        }
        tree = new Object[initCapacity];
    }

    @SuppressWarnings("unchecked")
    public boolean add(T v) {
        if (v == null) {
            return false;
        }
        if (!ensureCapacity(count + 1)) {
            return false;
        }
        tree[++count] = v; // add to heap tail
        int k = count;
        while (k > 1) {
            int parent = k >> 1; // index of parent
            T p = (T) tree[parent];
            if (order == MAX_HEAP) {
                if (p.compareTo(v) >= 0) { // parent >= v, no need swap
                    break;
                }
            } else {
                if (p.compareTo(v) <= 0) { // parent <= v, no need swap
                    break;
                }
            }
            tree[parent] = v; // swap
            tree[k] = p;

            k = parent;
        }
        return true;
    }

    @SuppressWarnings("unchecked")
    public T removeRoot() {
        final T root = getRoot();
        if (root == null) {
            return null;
        }
        tree[1] = tree[count]; //  move tail to root
        tree[count] = null; // free tail element
        count--;

        if (count < 1) {
            return root;
        }

        int k = 1;
        int leftChild = 2; // index of left child
        T newRoot = (T) tree[1];
        while (leftChild <= count) {
            T left = (T) tree[leftChild];
            // select max between left and right children
            int max = leftChild;
            if (leftChild < count) {
                T right = (T) tree[leftChild + 1];
                if ((order == MAX_HEAP && right.compareTo(left) > 0) || (order == MIN_HEAP && right.compareTo(left) < 0)) {
                    max++;
                }
            }
            T m = (T) tree[max];
            if ((order == MAX_HEAP && m.compareTo(newRoot) <= 0) || (order == MIN_HEAP && m.compareTo(newRoot) >= 0)) {
                break;
            }

            tree[k] = m; // swap
            tree[max] = newRoot;
            k = max;

            leftChild = k << 1;
        }
        return root;
    }

    @SuppressWarnings("unchecked")
    public T getRoot() {
        if (count == 0) {
            return null;
        }
        return (T) tree[1];
    }

    private boolean ensureCapacity(int target) {
        if (target > tree.length) {
            try {
                tree = Arrays.copyOf(tree, target);
            } catch (Exception e) {
                e.printStackTrace();
                return false;
            }
        }
        return true;
    }

    public int getCount() {
        return count;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= count; i++) {
            sb.append(tree[i].toString());
            if (i != count) {
                sb.append(",");
            }
        }
        return sb.toString();
    }
}

测试一下:

 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

public static void main(String[] args) {
    Heap<Integer> maxHeap = new Heap<>(Heap.MAX_HEAP, 10);
    Heap<Integer> minheap = new Heap<>(Heap.MIN_HEAP, 10);
    System.out.println("=========== max heap ===========");
    test(maxHeap);
    System.out.println("=========== min heap ===========");
    test(minheap);
}

private static void test(Heap<Integer> heap) {
    heap.add(18);
    System.out.println(heap);
    heap.add(40);
    System.out.println(heap);
    heap.add(60);
    System.out.println(heap);
    heap.add(45);
    System.out.println(heap);
    heap.add(32);
    System.out.println(heap);
    heap.add(22);
    System.out.println(heap);
    heap.add(36);
    System.out.println(heap);
    heap.add(50);
    System.out.println(heap);
    heap.add(30);
    System.out.println(heap);

    System.out.println("========start remove=======");

    final int count = heap.getCount();
    for (int i = 0; i < count; i++) {
        System.out.println(heap);
        heap.removeRoot();
    }
}
Support the author with
alipay QR Code
wechat QR Code
Yang
WRITTEN BY
Yang
Developer