曼哈顿
上篇文章写了二叉堆的几个方面（数据结构：二叉堆 ），包括：
堆的历史地位和作用
二叉堆的定义
二叉堆的数组索引规律
本篇文章学习二叉堆自我调整的两个核心操作：向上调整（shiftUp）和向下调整（shiftDown）。
向上调整（shiftUp）的使用场景是二叉堆 插入节点时，先把插入的节点放入二叉堆的最后一个位置，然后根据根据二叉堆的定义，把当前节点与父节点进行比较，对小顶堆来说，如果当前节点小于父节点，则当前节点移动到父节点的位置。
向下调整（shiftDown）的使用场景是二叉堆 删除节点时，将堆顶位置的节点删除，最后一个节点放到堆顶的位置。然后根据根据二叉堆的定义，把当前节点与子节点中最小的节点进行比较，对小顶堆来说，如果当前节点大于子节点中最小的节点，则当前节点移动到子节点中最小的节点的位置。
我们图文并茂演示一下二叉堆的插入节点操作：
一个最小二叉堆，插入节点0，插入位置是完全二叉树的最后一个位置。 这时，新节点的父节点5比0大，显然不符合最小堆的性质。于是让新插入节点向上调整（shiftUp），和父节点交换位置。
当前节点0和父节点3做比较，因为0小于3，不符合小顶堆原则，则让0节点继续向上调整（shiftUp）到父节点的位置。
当前节点0和父节点1做比较，因为0小于1，不符合小顶堆原则，则让0节点继续向上调整（shiftUp）堆顶的位置。
向上调整（shiftUp）代码实现：
def siftUp(array):
child_index = len(array) - 1//插入节点的位置
parent_index = (child_index - 1) // 2
temp = array[child_index] //临时变量存连续交换的新插入节点
while child_index > 0 and temp < array[parent_index]:
array[child_index] = array[parent_index]//覆盖即可，不进行真实交换
child_index = parent_index
parent_index = (parent_index - 1) // 2
array[child_index] = temp//交换结束，插入节点直接放入最终位置即可
void shiftUp(int* arr, int n, int cur)
{
int parent = (cur - 1) / 2;
//假定倒数第一个叶子节点为当前节点cur，找出它的父节点
while (cur > 0)
{//比较父节点和当前节点。当前节点小的话，则不满足小堆规则，需要进行交换
if(arr[cur] < arr[parent])
{
Swap(&arr[cur], &arr[parent]);
cur = parent;
parent = (cur - 1) / 2;
}
else
{
break;
}
}
}
我们图文并茂演示一下二叉堆的删除节点操作：
二叉堆删除节点的过程和插入节点的过程正好相反，所删除的是处于堆顶的节点。例如删除最小堆的堆顶节点1。这时，为了继续维持完全二叉树的结构，我们把堆的最后一个节点10临时补到原本堆顶的位置。
接下来，让暂处堆顶位置的节点10和它的左、右孩子进行比较，如果左、右孩子节点中最小的一个（显然是节点2）比节点10小，那么让节点10向下调整（shiftDown）。继续让节点10和它的左、右孩子做比较，左、右孩子中最小的是节点7，由于10大于7，让节点10继续向下调整（shiftDown）。
向下调整（shiftDown）代码实现：
def shiftDown(array):
parent_index = 0
temp = array[parent_index]
child_index = 2 * parent_index 1
while child_index < len(array):
if child_index 1 < len(array) and array[child_index 1] < array[child_index]:
child_index = 1
if temp <= array[child_index]:
break
array[parent_index] = array[child_index]
parent_index = child_index
child_index = 2 * parent_index 1
array[parent_index] = temp
void shiftDown(int* arr, int n, int cur)
{
int child = 2 * cur 1;
while (child < n)
{
//比较左右子树，找到较小值
if(child 1 < n && arr[child 1] < arr[child])
{
child;
// child时刻保存较小值的下标
}
if(arr[child] < arr[cur])
{
Swap(&arr[child], &arr[cur]);
cur = child;
child = 2 * cur 1;
}
else
{
break;
}
}
}
下一篇学习，优先队列。
,
