乐趣区

关于ide:扫盲数据结构-堆入门

jiezi

什么是堆

  • 堆是一颗【齐全二叉树】
  • 堆的所有【根节点 】“大于”【 子节点】

    这里的大于是能够定义的。

<img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318211957067.png” alt=”image-20200318211957067″ style=”zoom:50%;” />

​ 上图所示，都是满足堆上方的性质，一颗齐全二叉树，所有的根节点大于子节点

​ 上方展现的为最大堆（相应的也能够定义最小堆）

  • 应用数组示意

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318212734956.png” alt=”image-20200318212734956″ style=”zoom:50%;” />

    因为堆满足齐全二叉树的定义，所以堆能够应用数组来示意【上图所示】。

    由上图得在 index 地位上的节点能够推倒出如下公式 parent(i) = i / 2 left child (i) = 2 * i right child (i) = 2 * i + 1

    然而在上图中，其实是节约了数组的零号地位，如果元素从 0 号地位排将会是上面的构造

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318213435336.png” alt=”image-20200318213435336″ style=”zoom:50%;” />

    由上图能够推倒公式为：

    parent(i) = (i - 1) / 2 left child (i) = 2 * i + 1 right child (i) = 2 * i + 2

堆中的罕用操作

  • Sift Up（向堆中增加元素）

    上浮，因为堆底层实现为数组，所以咱们在增加元素的时候是间接向数组的末端增加元素，这样就始终保障堆是一个齐全二叉树，然而咱们须要维持二叉树第二个性质，根节点元素大于子节点，所以咱们须要 sift up 操作

    假如有如下堆构造：

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318214332416.png” alt=”image-20200318214332416″ style=”zoom:50%;” />

    假如咱们当初须要增加的元素为 52，当初元素的地位为 arr[arr.length - 1]，然而这样就违反了堆的构造，因为 52 > 16，sift up 就是如果以后元素大于根节点元素的值那么就替换两个元素，【迭代】执行，直到满足子节点小于根节点。

    这时咱们就须要替换 52 和 16 号元素的值

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318214919048.png” alt=”image-20200318214919048″ style=”zoom:50%;” />

    替换实现后是这个样子

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318215227768.png” alt=”image-20200318215227768″ style=”zoom:50%;” />

    然而这时候又会发现还是不满足堆构造，因为 52 > 41，所以 52 和 41 还须要替换

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318215332914.png” alt=”image-20200318215332914″ style=”zoom:50%;” />

    替换后才又满足堆的构造

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318215450242.png” alt=”image-20200318215450242″ style=”zoom:50%;” />

    下面 52 号元素挪动的整个过程，称之为 sift up 上浮

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/heap_sift_up.png” style=”zoom:80%;” />

  • Sift Down（取出堆中的最大元素）

    由堆的个性所得，根节点的元素为堆中的最大元素，所以咱们只须要取出根节点即可。

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318220445853.png” alt=”image-20200318220445853″ style=”zoom:50%;” />

    然而如果间接取出根节点就会导致将原来的堆切割为两个堆，后续在合并的时候就会变的异样麻烦，所以咱们这里转变一下思路，间接将开端的元素 arr[arr.length – 1] 16 与 根节点 62 替换地位，而后再将其解决为堆构造这样会简略很多

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318220722116.png” alt=”image-20200318220722116″ style=”zoom:50%;” />

    如上图所示，间接将开端的元素替换掉头结点。此时就违反了堆构造，咱们就须要进行 Sift Down 的操作。

    以后元素与它的左右孩子进行比照，与左右孩子中较大的孩子进行替换，迭代进行，最终便可实现 Sift Down

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318221110695.png” alt=”image-20200318221110695″ style=”zoom:50%;” />

    第一次替换 16 和 50，因为 52 > 30，替换后的成果为

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318221300114.png” alt=”image-20200318221300114″ style=”zoom:50%;” />

    第二次 替换 16 和 42，因为 42 > 16

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318221601439.png” alt=”image-20200318221601439″ style=”zoom:50%;” />

    通过后面的两次替换后，当初就满足最大堆的性质了。

    下面两次替换的过程就称为 Sift Down

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/heap_sift_down.png” style=”zoom:80%;” />

  • replace
  • heapity

本文由博客群发一文多发等经营工具平台 OpenWrite 公布

退出移动版