一组记录关键字为(5,11,7,2,3,17),如何利用堆排序方法建立初始大根堆,给出你建立的初始大根堆对应的关键字序列。
时间: 2024-05-30 07:11:03 浏览: 25
可以按照以下步骤建立初始大根堆:
1. 将记录依次插入一个空堆中,此时堆中只有一个元素,直接返回该元素,即为初始大根堆。
2. 从第二个元素开始,依次将元素插入初始大根堆中。
3. 每次插入一个元素时,将该元素放在堆的最后一个位置,然后比较该元素与其父节点的大小关系,如果该元素大于其父节点,则将该元素与其父节点交换位置。
4. 重复步骤3,直到该元素不再大于其父节点,或者到达堆顶。
根据上述步骤,可以得到以下初始大根堆对应的关键字序列:
17, 5, 11, 2, 3, 7
相关问题
一组记录的排序码为(4,8,6,7,10,3,5),则利用堆排序方法建立的初始堆(大根堆)为________。
堆排序是一种树形选择排序,其基本思想是将待排序序列构造成一个堆,根据堆顶元素的关键字选择最大或最小元素,并将其与堆底元素交换,然后将剩余的元素重新构造成一个堆,如此重复,直到整个序列有序。在建立初始堆时,可以考虑从最后一个非叶子节点开始调整堆,使得整个堆满足大根堆的性质。以下是一组记录的排序码为(4,8,6,7,10,3,5),利用堆排序方法建立的初始堆的过程:
1. 从最后一个非叶子节点开始调整堆,因此从节点7(即10的父节点)开始,向前依次对每个非叶子节点进行堆调整。
2. 对节点7进行堆调整,发现节点7的值为7,节点15(即3的父节点)的值为10,因此需要将节点7和节点15进行交换,交换后的序列为(4,8,6,10,7,3,5)。
3. 对节点3进行堆调整,发现节点3的值为6,节点7的值为10,因此需要将节点3和节点7进行交换,交换后的序列为(4,8,10,6,7,3,5)。
4. 对节点1进行堆调整,发现节点1的值为8,节点3的值为10,因此需要将节点1和节点3进行交换,交换后的序列为(4,10,8,6,7,3,5)。
5. 对节点0进行堆调整,发现节点0的值为4,节点1的值为10,因此需要将节点0和节点1进行交换,交换后的序列为(10,4,8,6,7,3,5)。
6. 经过上述操作,建立的初始堆为(10,4,8,6,7,3,5),满足大根堆的性质。
若一组记录的关键码为(46,79,56,38,40,84),请写出利用堆排序的方法建立的初始堆。请写详细过程(3分)和结果(3分),
利用堆排序的方法建立初始堆的过程如下:
1. 将记录依次插入空堆中,插入的方法是比较插入节点和父节点的大小关系,若插入节点较小,则交换两者的位置,一直到根节点为止。
2. 对于关键码为(46,79,56,38,40,84),依次插入空堆中,建立初始堆的过程如下:
- 插入46,堆为46
- 插入79,堆为79, 46
- 插入56,堆为79, 46, 56
- 插入38,堆为79, 46, 56, 38
- 插入40,堆为79, 46, 56, 38, 40
- 插入84,堆为84, 79, 56, 38, 40, 46
建立的初始堆为:84, 79, 56, 38, 40, 46。
注意:这里的堆是指二叉堆,即每个节点最多只有两个子节点,且父节点的关键码大于等于子节点的关键码(大根堆)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)