数据结构：二叉堆的自我调整

曼哈顿

上篇文章写了二叉堆的几个方面（数据结构：二叉堆 ），包括：

堆的历史地位和作用

二叉堆的定义

二叉堆的数组索引规律

本篇文章学习二叉堆自我调整的两个核心操作：向上调整（shiftUp）和向下调整（shiftDown）。

向上调整（shiftUp）的使用场景是二叉堆 插入节点时，先把插入的节点放入二叉堆的最后一个位置，然后根据根据二叉堆的定义，把当前节点与父节点进行比较，对小顶堆来说，如果当前节点小于父节点，则当前节点移动到父节点的位置。

向下调整（shiftDown）的使用场景是二叉堆 删除节点时，将堆顶位置的节点删除，最后一个节点放到堆顶的位置。然后根据根据二叉堆的定义，把当前节点与子节点中最小的节点进行比较，对小顶堆来说，如果当前节点大于子节点中最小的节点，则当前节点移动到子节点中最小的节点的位置。

我们图文并茂演示一下二叉堆的插入节点操作：

一个最小二叉堆，插入节点0，插入位置是完全二叉树的最后一个位置。 这时，新节点的父节点5比0大，显然不符合最小堆的性质。于是让新插入节点向上调整（shiftUp），和父节点交换位置。

当前节点0和父节点3做比较，因为0小于3，不符合小顶堆原则，则让0节点继续向上调整（shiftUp）到父节点的位置。

当前节点0和父节点1做比较，因为0小于1，不符合小顶堆原则，则让0节点继续向上调整（shiftUp）堆顶的位置。

向上调整（shiftUp）代码实现：

我们图文并茂演示一下二叉堆的删除节点操作：

二叉堆删除节点的过程和插入节点的过程正好相反，所删除的是处于堆顶的节点。例如删除最小堆的堆顶节点1。这时，为了继续维持完全二叉树的结构，我们把堆的最后一个节点10临时补到原本堆顶的位置。

接下来，让暂处堆顶位置的节点10和它的左、右孩子进行比较，如果左、右孩子节点中最小的一个（显然是节点2）比节点10小，那么让节点10向下调整（shiftDown）。继续让节点10和它的左、右孩子做比较，左、右孩子中最小的是节点7，由于10大于7，让节点10继续向下调整（shiftDown）。

向下调整（shiftDown）代码实现：

下一篇学习，优先队列。