二叉堆

概念

堆是一个可以被看作近似完全二叉树的数组。树上的每一个节点对应数组的一个元素。出了最底层外，该树是完全充满的，而且是从左到右填充哦。 –《算法导论》

堆包括最大堆和最小堆

最大堆的每一个节点(根节点除外)的值，不大于其父节点。
最小堆的每一个节点(根节点除外)的值，不小于其父节点。

屏幕快照 2020-05-29 下午5.51.23

堆的常见操作

heapify 原地建堆：把一个乱序的数组变成堆结构的数组, 时间复杂度 O(N)
add 添加元素: 把一个数值放进已经是堆结构的数组中，并维持堆的结构, 时间复杂度O(log N)
remove 删除堆顶元素 : 把堆顶元素删除，并将剩余的数组为堆结构, 时间复杂度 O(log N)
get 获取堆顶元素: 获取堆顶元素, 时间复杂度 : O(1)
replace 删除堆顶元素的同时插入一个新元素, 时间复杂度 O(log N)

堆的常见应用

Java中的优先级队列 (Priority Queue)
Top K问题 (获取最大或最小的前 K 个数）
堆排序 (时间复杂度 O (N * long N))

底层结构

二叉堆的逻辑结构就是一颗完全二叉树, 所以也叫完全二叉堆。

鉴于完全二叉树的性质, 二叉堆的底层(物理结构), 一般采用数组即可。
索引 i 的规律 (N 为元素数量)
- 如果 i == 0 , 它是根节点 (堆顶)
- 如果 i > 0, 它的父节点索引为 floor((i - 1) / 2)
- 如果 2i + 1 <= N - 1, 则它左子节点的下标为 2i + 1
- 如果 2i + 1 > N - 1, 则它无左子节点
- 如果 2i + 2 <= N - 1, 则它的右子节点下标为 2i + 2
- 如果 2i + 2 > N - 1, 则它无右子节点

基本接口设计

以下所有操作，以最大堆为例

元素的数量

直接返回元素的size即可

1
2
3


    public int size() {
        return size;
    }

是否为空

size == 0为空，否则不为空

1
2
3


    public boolean isEmpty() {
        return size == 0;
    }

清空

遍历数组清空， size 置为0 即可

1
2
3
4
5
6


    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

添加元素

// 添加到末尾，再上滤该元素，直到 该元素 < 父元素 或者 到达堆顶

1
2
3
4
5
6
7
8


    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size + 1);

        elements[size++] = element;
        siftUp(size-1);
    }

获取堆顶元素

1
2
3
4


    public E get() {
        emptyCheck();
        return elements[0];
    }

删除堆顶元素

// 用 末尾元素 代替 堆顶元素，将末尾元素清空，再将新的堆顶元素下滤。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    public E remove() {
        emptyCheck();

        E root = elements[0];
        int lastIdx = --size;
        elements[0] = elements[lastIdx];
        elements[lastIdx] = null;

        siftDown(0);
        return root;
    }

替换堆顶元素

新元素替换堆顶元素，再将新的堆顶元素下滤

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


    public E replace(E element) {
        elementNotNullCheck(element);

        E root = null;
        if (size == 0){
            elements[0] = element;
            size ++;
        }else{
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }
        return root;
    }

批量建堆(Heapify)

自上而下的上滤

屏幕快照 2020-05-29 下午6.26.48

自下而上的下滤

屏幕快照 2020-05-29 下午6.26.53

效率对比

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    private void heapify(){
        // 自上而下的上滤
//        for (int i = 1; i < size; i++) {
//            siftUp(i);
//        }

        // 自下而上的下滤
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

上滤

元素依次与父节点对比, 如果比父节点大，则替换父节点, 继续上滤。直到到达堆顶 或者 比父节点小为止

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



    // 上滤
    private void siftUp(int index){

        E element = elements[index];
        while (index > 0){
            int pIdx = (index - 1) >> 1;
            E parE = elements[pIdx];

            if (compare(element,parE) >= 0) break;
            elements[index] = parE;

            index = pIdx;
        }

        elements[index] = element;
    }

下滤

节点值与其 左右子节点中的较大者 比较, 如果比子节点值小, 则交换，直到比左右父节点都大，或者成为叶子节点

 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


// 下滤
    private void siftDown(int index){
        E element = elements[index];

        // 非叶子节点 子节点比较 交换
        // index < 第一个叶子结点的索引
        // index < 非叶子结点的数量
        int half = size >> 1;
        while (index < half){
            // index的结点有两种情况
            // 只有左子节点
            // 左右子节点都有

            // 默认取出左子节点的值跟element比较
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];

            // 右子节点
            int rightIndex = childIndex + 1;
            if (rightIndex < size && compare(elements[rightIndex],child) > 0){
                child = elements[childIndex = rightIndex];
            }
            // 子节点小
            if (compare(element,child) >= 0) break;
            // 子结点大 交换
            elements[index] = child;
            index = childIndex;
        }
        elements[index] = element;
    }

Contents

二叉堆

概念