数据结构大根堆小根堆例题（二叉堆的自我调整）

曼哈顿

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

堆的历史地位和作用

二叉堆的定义

二叉堆的数组索引规律

本篇文章学习二叉堆自我调整的两个核心操作：向上调整（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; } } }

下一篇学习，优先队列。