题13

题13

题目

Q:已知大根堆 ,删除堆顶元素后需要重新调整堆,则在此过程中关键字的比较次数为 ( ) .
A. 2 B. 3 C. 4 D. 5

分析

A:堆的删除过程是通过交换，然后下沉实现的
居然第一次比较是两个叶子结点的比较，小根堆也是这样吗，小根堆也是的，每次是从左根右里面最小的那个进行替换
好的，我们来模拟一下从以下小根堆中删除根节点（最小元素）的过程：

        1
     /     \
   2         3
  /  \      / \
 5    4    8   6 
/ \   
7  9

步骤1：用最后一个节点替换根节点
首先，我们将最后一个节点（值为 9 的节点）的值复制到根节点，并将最后一个节点删除：

        9
     /     \
   2         3
  /  \      / \
 5    4    8   6 
/ 
7  

步骤2：向下调整新的根节点
现在，我们需要将新的根节点（值为 9 的节点）向下调整到合适的位置，以维护小根堆的性质。

• 比较根节点与它的子节点： 节点 9 与它的子节点 2 和 3 进行比较。
• 选择最小的子节点： 节点 2 的值最小。
• 交换节点： 将节点 9 与节点 2 交换位置：

        2
     /     \
   9         3
  /  \      / \
 5    4    8   6 
/ 
7  

• 继续向下调整： 现在，节点 9 成为了节点 2 的左子节点。我们重复上述过程，比较节点 9 和它的子节点 5 和 4。
• 选择最小的子节点： 节点 4 的值最小。
• 交换节点： 将节点 9 与节点 4 交换位置：

        2
     /     \
   4         3
  /  \      / \
 5    9    8   6 
/ 
7  

• 继续向下调整： 现在，节点 9 成为了节点 4 的右子节点。我们再次重复以上过程，比较节点 9 和它的子节点 7。
• 选择最小的子节点： 节点 7 的值最小。
• 交换节点： 将节点 9 与节点 7 交换位置：

        2
     /     \
   4         3
  /  \      / \
 5    7    8   6 
/ 
9  

此时，节点 9 已经成为了一个叶子节点，不需要再进行向下调整。

解

B
删除堆顶 62 后, 将堆尾 22 放入堆顶, 然后自上而下调整。
首先 34 与 53 比较 (第一次比较), 较大者 53 与根 22 比较 (第二次比较), 53 被换至堆顶; 22 只有一个孩子, 直接与其左孩子 46 比较 (第 3 次比较), 22 与 46 交换, 至此大根堆调整结束, 具体过程如下图所示。