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

数据结构大根堆小根堆例题(二叉堆的自我调整)(1)

曼哈顿

上篇文章写了二叉堆的几个方面(数据结构:二叉堆 ),包括:

堆的历史地位和作用

二叉堆的定义

二叉堆的数组索引规律

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

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

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

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

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

数据结构大根堆小根堆例题(二叉堆的自我调整)(2)

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

数据结构大根堆小根堆例题(二叉堆的自我调整)(3)

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

数据结构大根堆小根堆例题(二叉堆的自我调整)(4)

向上调整(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临时补到原本堆顶的位置。

数据结构大根堆小根堆例题(二叉堆的自我调整)(5)

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

数据结构大根堆小根堆例题(二叉堆的自我调整)(6)

向下调整(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; } } }

下一篇学习,优先队列。

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。