已知关键字序列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

[tag_link]

正确答案：A

根据关键字序列得到的 小根堆 的二叉树形式如下图所示。

5 8 12 19 28 20 15 22 5 8 12 19 28 20 15 22 3 3 5 12 8 28 20 15 22 19 (1) (2) (3) 插入关键字 3 时，先将其放在小顶堆的末端，如图 (2) 所示。

再将该关键字向上进行调整，得到的结果如图 (3) 所示。

所以，调整后的小顶堆序列为 3, 5, 12, 8, 28, 20, 15, 22, 19。