一个小根堆的序列为:{5, 12, 7, 1...

[单选题]

一个小根堆的序列为:{5, 12, 7, 18, 31, 13, 9}，删除根节点5之后，小根堆会自动调整重新变为小根堆，小根堆的最后的叶子节点为?

```
31
```
```
13
```
```
9
```
```
12
```
```
18
```

查看正确选项

夏至未央

删除根节点（删除最小节点）：首先删除根节点5，堆为 “空 12 7 18 31 13 9”，然后考察最后一个叶节点9能否填入空位（保证填入后依然是小根堆），如果能，则将该叶节点填入空位；如果不能，则将空位的两个子节点中较小的一个填入空位，然后对新的空位进行同样的的操作。9比根节点5（已删除）下面的两个子节点12和7中比7大不能填入，则找根节点（5 已删除）的子节点12和7。发现7小填入，此时堆为“7 12 空 18 31 13 9”，此时对7的右子节点空处理，找最后一个叶节点9，填入发现比剩下的13小，可以，填入此时堆为“7 12 9 18 31 13”，最后一个叶子结点是13。这是搜了资料自己的理解，希望可以帮助你们。

发表于 2022-04-12 11:44:35 回复(1)