堆数据结构详解-CSDN博客

本文链接：https://blog.csdn.net/vectorX/article/details/104218009

堆的产生

堆的产生问题背景：如何在一堆动态变化的数中，以O(1)的复杂度获取最值。

堆的目标：一个数组，支持删除元素和添加元素，保证首元素永远是数堆中的最值。

数组树形化：比如给出数组 $[7,9,8,1,10]$ ，一层一层依次从左到右加入节点，构造出如下图所示的一颗树，该种树形称为完全二叉树。

对于数组 $a$ ，其所有元素的父子关系满足 $\left\{\begin{matrix} a[i].l = a[2*i+1] \\ a[i].r = a[2*i+2] \end{matrix}\right. ,(2*i+1>=a.length,null)$ 。

完全二叉树：每一层节点都是满的，最底下一层叶子节点从左到右也是满的。

完全二叉树的数组化：可以用数组存储，按层次从左到右遍历树节点。比如下图。

堆的定义：

逻辑上是一个完全二叉树，支持删除元素和添加元素，保证根元素永远是数堆中的最值。其所有子树也都是堆。
物理存储上，因为完全二叉树的节点可由数组存储，所以是一个数组，所有节点的父/子节点在数组中的位置，可由公式计算得到。以 $[7,9,8,1,10]$ 为例，数组位置从 0 开始计。 $9$ 的位置是 $1$ ，其父节点位置是 $$\lfloor 1/2 \rfloor$ = 0$ ，左子节点下标是 $2*1+1 = 3$ ，右子节点下标是 $2*1+ 2= 4$ 。

堆示例： $[7,9,8,1,10]$ 就不是堆，因为 $7$ 不是最值，且以 $9$ 为根的子树，根也不是最值。 $[10,9,8,1,7]$ 是堆，树形化后如下图所示：

建堆

建堆的目标：以前面的数组 $[7,9,8,1,10]$ 为例，调整元素位置，使之对应的完全二叉树，符合堆定义。

建堆的思路：把问题分解，从最小的树开始调整。

先找到完全二叉树中最低层的父节点。按父子关系公式逆运算，元素下标是 $\lfloor len/2 \rfloor$ ，就是 $9$ 。该树只有最多三个节点，父节点与子节点中最大的节点互换位置，如果父节点最大就按兵不动。此时该元素( $9$ )为根的子树满足堆定义。
继续往前调整节点，此时元素下标是 $$\lfloor len/2 \rfloor$ -1$ ，就是 $7$ ，父子节点进行同样的比较互换操作 $(7,10,8)$ ，如果有更换( $10$ 与 $7$ 互换了)，那么无法保证新的子节点值 $7$ 是子树的最大值，所以需要继续将该子节点 $7$ 和其子节点 $1,9$ 进行同样的比较互换操作，一直进行到比较时无需更换，或者没有子节点为止。
继续往前发现已经到数组首元素前面了，结束。
前面对节点 $7$ 一路向下的比较调整，称为向下调整。而前面从最低父节点 $9$ 开始的建堆，我自称为向前建堆。