关键码序列(503,087,512,061,908,170,897,275,653,426)堆排序第一趟后结果序列是什么
时间: 2024-02-02 18:36:03 浏览: 21
堆排序的第一趟是将给定序列构建成一个最大堆。最大堆是一种满足父节点大于等于左右子节点的完全二叉树。
首先,将给定序列构建成一个完全二叉树:
```
503
/ \
087 512
/ \ / \
061 908 170 897
/ \
275 653
```
接着,从最底层非叶子节点开始,逐步向上调整每个子树,使之成为最大堆。
```
503
/ \
908 512
/ \ / \
061 087 170 897
/ \
275 653
```
因此,堆排序的第一趟后结果序列为:908,503,512,061,087,170,897,275,653,426。
相关问题
关键码序列(503,087,512,061,908,170,897,275,653,426)堆排序第一趟后结果是什么
堆排序的第一趟是将关键码序列构建成一个大根堆。建堆的过程如下:
1. 从最后一个非叶子节点开始,逐个向上调整子树,使每个子树都满足大根堆的性质。
最后一个非叶子节点的下标为 (n/2)-1,其中 n 为序列长度。在这个序列中,最后一个非叶子节点的下标为 3。
对于下标为 i 的节点,其左子节点的下标为 2*i+1,右子节点的下标为 2*i+2。
2. 调整完最后一个非叶子节点后,将根节点与最后一个节点交换。
此时,最后一个节点已经是当前序列中最大的元素,它就是堆的最大值。将其放在序列尾部,并将序列长度减一。
经过第一趟排序后,关键码序列变为:[908, 503, 897, 061, 426, 170, 512, 275, 653]。
关键码序列(503,087,512,061,908,170,897,275,653,426)堆排序第二趟后结果是什么
堆排序第二趟是将堆顶元素(最大值)与最后一个元素交换,然后重新构建堆。在第一趟结束后,堆顶元素为908,最后一个元素为426。
交换堆顶元素和最后一个元素后,关键码序列变为:(426,087,512,061,908,170,897,275,653,503)
重新构建堆后,堆顶元素为最大值512。
因此,堆排序第二趟后的结果是512。