2,5,16,28,8,25,4,10,20,6,18 为该序列建立初始小根堆
时间: 2023-10-18 19:04:15 浏览: 61
同样的,我们按照小根堆的定义,建立初始小根堆的步骤如下:
1. 将序列按照顺序依次插入二叉树中,从上到下、从左到右依次填满每一层,直到最后一层。
2. 从最后一个非叶子节点(即编号为 n/2 的节点,其中 n 为总节点数)开始,向上遍历每个节点,对于每个节点,如果它的值小于它的子节点的值,则将该节点与其子节点中值最小的一个交换,直到该节点满足小根堆的条件。
根据上述步骤,我们可以得到以下初始小根堆:
```
2
/ \
5 4
/ \ / \
10 8 16 28
/ \ /
20 25 18
```
其中根节点为 2,每个节点都小于等于它的子节点。
相关问题
12,5,16,28,8,25,4,10,20,6,18为该序列建立初始小根堆
初始序列为:12,5,16,28,8,25,4,10,20,6,18
建立初始小根堆的过程如下:
1. 从最后一个非叶子节点开始,即节点下标为 (n/2)-1 = 4 的节点(n为节点总数),依次向前遍历每个非叶子节点。
2. 对于每个非叶子节点,判断它与它的两个子节点的大小关系,并将最小的节点上移。
3. 经过一次遍历后,序列变为:12,5,16,10,8,25,4,28,20,6,18
4. 继续遍历非叶子节点,直到根节点。经过第二次遍历后,序列变为:4,5,6,10,8,25,16,28,20,12,18
5. 最终得到的初始小根堆为:
4
/ \
5 6
/ \ \
10 8 16
/ \ / / \
28 20 12 18 25
12,5,16,28,8,25,4,10,20,6,18为该序列建立初始小根堆过程
建立初始小根堆的过程如下:
1. 将序列中的元素依次插入空堆中,得到以下完全二叉树:
```
4
/ \
/ \
5 16
/ \ / \
28 8 25 10
/ \ / \
20 6 18
```
2. 从最后一个非叶子节点开始,依次对其进行堆化操作。最后得到的堆即为初始小根堆。堆化过程如下:
- 对节点 5 进行堆化:
```
4
/ \
/ \
6 16
/ \ / \
28 8 25 10
/ \ / \
20 12 18
```
- 对节点 4 进行堆化:
```
4
/ \
/ \
6 16
/ \ / \
28 8 25 10
/ \ / \
20 12 18
```
- 对节点 3 进行堆化:
```
4
/ \
/ \
6 18
/ \ / \
28 8 25 10
/ \ / \
20 12 16
```
- 对节点 2 进行堆化:
```
4
/ \
/ \
6 18
/ \ / \
10 8 25 16
/ \ / \
20 12 28
```
- 对节点 1 进行堆化:
```
4
/ \
/ \
6 18
/ \ / \
10 8 25 16
/ \ / \
20 12 28
```
- 对节点 0 进行堆化:
```
4
/ \
/ \
6 18
/ \ / \
10 8 25 16
/ \ / \
20 12 28
```
最终得到的初始小根堆为:
```
4
/ \
/ \
6 18
/ \ / \
10 8 25 16
/ \ / \
20 12 28
```