二叉堆原理与实现

二叉堆

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

结构性质

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

以上图为例, 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

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

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

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

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

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--; } 

书上的解法

1. 首先将last element赋值给array[1]
2. 将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]);     //        } }  

参考

<数据结构与算法分析 Java描述> 6.3 BinaryHeap
完全二叉树看起来并不完全，为什么叫完全二叉树呢？
https://blog.csdn.net/qq_42006733/article/details/104580717