二叉堆原理与实现

有品 / 2023-07-24 / 原文

二叉堆

二叉堆具有两个性质, 结构性和排序性.

结构性质

堆是一棵被完全填满的二叉树, 叫做完全二叉树, 除了底层以外都被填满了, 而最底层从左到右填入了.

以上图为例, 1是小顶堆, 2是大顶堆, 3是小顶堆, 4不是堆.
这种完全二叉树并不一定被填满, 为什么要被称作是完全二叉树呢? 这是因为这种二叉树可以被高效的保存在数组中. 二叉树通常有两种方式存储:

基于链表

每个节点存储3个字段

基于数组

这种方式中根节点存储在1位, 后面左节点存储在 2i位, 右子节点存储在2i+1位. 通过这种方式只要知道根节点的位置, 就可以利用上述的关系构建出整个树, 这样的存储非常的紧密, 不需要额外存储左右指针.
但是如果二叉树不是满二叉树按照这种方式存储就会存在空洞, 造成空间浪费

回到堆的话题, 因为堆满足完全二叉树的结构性, 所以通常堆都是存储在数组中.

堆序性质

在一个堆(小根堆)中, 对于每一个节点X, X的父亲节点 <= X节点

如上图右侧的完全二叉树就不是堆.

从上面定义的信息可以看出堆所提供的有序性是有限的, 只能知道堆顶是最大或最小值, 因此堆最常用的就是用作优先级队列, 优先级队列所需要的接口.

add
findMin
deleteMin

在添加和删除的时候都需要去维护上面提到的两个堆的性质.

实现

add

新插入的值默认插在末尾, 这会破快堆的有序性, 所以需要找到合适的位置放置新加入的值. 将插入的值逐步和parent比较, 如果小于parent 则上浮

样例实现

public void add(int x) {
    if (size == elements.length - 1) {
    enlargeArray();
}

// 复制elements[0]的好处是for循环不需要对 index 0 特殊处理
// i = 1时, 就会和elements[0] 作比较
elements[0] = x;
// percolate up / sift up
// i 要从 ++size算起, 不然找的parent可能是错的
for (int i = ++size; i >= 1; i = i / 2) {
    // 插入值小于父节点, 将父节点下移, 空穴上移
    if (x < elements[i / 2]) {
        elements[i] = elements[i / 2];
    } else {
        elements[i] = x;
        break;
    }
}
}

deleteMin

删除最小值后, 根节点就变成了空值, 为了保障堆的结构性, 将最后一位填充到根节点处, 同时这不一定满足堆序性质, 所以要和左右子树逐步比较下沉.

这里我开始思考的是另一种思路实现

判断是否右子树为空或者左子树小于右子树, 如果是则左子树上移, 否则右子树上移
退出条件为移动到没有子树的节点即 i > size /2
退出后将最后一位赋值给当前值

需要注意的是左右子树不一定都存在

private void deleteMin() {
    int i = 1;
    if (size == 1) {
        size = 0;
        return;
    }
    for (; i <= size / 2;) {
        // 右子树为空或者左子树小于右子树
        if (2 * i + 1 > size || elements[2 * i] < elements[2 * i + 1]) {
            // 左子树上移
            elements[i] = elements[2 * i];
            i = 2 * i;
        } else {
            elements[i] = elements[2 * i + 1];
            i = 2 * i + 1;
        }
    }

    elements[i] = elements[size];
    size--;
}

书上的解法

首先将last element赋值给array[1]
将array[1] 下沉

这两种实现差别

第一种的思路是不断的在两个子树中查找较小值提升
第二种思路是将末尾设置为root后, 不断地将这个值下沉, 第二种更符合算法的 percolate down的描述. 而且第一种一定会比较logN次, 而第二种实际上是可能会提前终止的. 所以第二种的最优运行情况中的比较次数会更少

打印

同样添加了一个方法来打印堆的结构方便检验准确性

private void print() {
    int currentLevel = 0;
    int currentIndent = 0;
    int totalLevel = (int) Math.floor(Math.log(size) / Math.log(2)) + 1;
    StringBuilder levelBuilder = new StringBuilder();
    levelBuilder.append(String.format("level% 2d: ", currentLevel));
    for (int i = 1; i <= size; i++) {
        // 不精确的计算 log2(N)
        int level = (int) Math.floor(Math.log(i) / Math.log(2));
        if (level != currentLevel) {
            System.out.println(levelBuilder.toString());
            currentLevel = level;
            currentIndent = 0;
            levelBuilder = new StringBuilder();
            levelBuilder.append(String.format("level% 2d: ", currentLevel));
        }
        int toLeftIntent = indent(i, totalLevel - 1);
        levelBuilder.append(blank((toLeftIntent - currentIndent), currentLevel));
        currentIndent = toLeftIntent;
        levelBuilder.append(String.format("%d", elements[i]));
    }
    System.out.println(levelBuilder.toString());

    //        for (int i = 1; i <= size; i++) {
    //            System.out.printf("%d ", elements[i]);
    //        }
}