408考研逐题详解：2009年第9题

2009年第9题

已知关键字序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是（ ）

A. 3，5，12，8，28，20，15，22，19
B. 3，5，12，19，20，15，22，8，28
C. 3，8，12，5，20，15，22，28，19
D. 3，12，5，8，28，20，15，22，19

详解

本题涉及到以下知识点：

1. 小根堆：小根堆是一种特殊的完全二叉树，其中每个结点的关键字都小于或等于其子结点的关键字。这种结构保证了堆顶元素总是最小值。
2. 堆的插入操作：在堆中插入一个新元素时，通常将新元素添加到堆的末尾（即最后一个叶子结点之后），然后通过“上浮”操作来调整堆，使其称为小根堆（或大根堆）。

已知的小根堆，用完全二叉树表示，如下图中的（1）所示，将关键字 3 插入之后，即为图中（2）所示。而后对该堆进行调整，使其符合小根堆的性质，得到图（3）所示结果。

本题答案：A