若一组记录的排序码为若一组记录的排序码为(45,77,56,38,40,84),则利用堆排序的方法建立的初始堆为( ),说明过程
时间: 2023-08-31 10:36:10 浏览: 175
### 回答1:
(84,45,77,38,40,56)。使用堆排序的方法建立初始堆的步骤如下:1. 首先把序列中的元素依次插入堆中,这里的堆是一个完全二叉树,而且每个节点都要比它的子节点大;2. 从最后一个非叶子节点开始,将它和它的子节点进行比较,如果父节点大于子节点,则无需改动,如果父节点小于子节点,则交换它们的位置;3. 重复第二步,直到根节点,即可得出初始堆。因此,给出的序列(45,77,56,38,40,84)建立的初始堆为(84,45,77,38,40,56)。
### 回答2:
利用堆排序的方法建立初始堆的过程如下:
1. 将给定的一组记录的排序码依次插入空堆中,按照二叉树的特点,插入的顺序可以任意选择。
初始堆的建立过程如下:
- 第一个插入的元素是45,此时堆为空,将45作为根节点插入堆中。
45
/
/
77
- 第二个插入的元素是77,由于77比根节点45大,所以将77与45交换位置。
77
/
/
45
- 第三个插入的元素是56,与根节点77比较,小于77,不用交换位置,直接插入为77的左子节点。
77
/
56
/
/
45
- 第四个插入的元素是38,与根节点77比较,小于77,不用交换位置,与56比较,大于56,与56交换位置,然后插入为原来56的左子节点。
77
/
38
/ \
/ \
45 56
- 第五个插入的元素是40,与根节点77比较,小于77,不用交换位置,与56比较,小于56,与56交换位置,与45比较,大于45,与45交换位置,然后插入为原来45的左子节点。
77
/
40
/ \
/ \
56 38
- 第六个插入的元素是84,与根节点77比较,大于77,与77交换位置,然后插入为原来77的左子节点。
84
/
77
/ \
/ \
56 38
/
/
40
以上过程就是利用堆排序的方法建立初始堆的过程。
阅读全文