给定序列(67,45,87,19,55,32,70,60,90,23),写出它的初始堆(大根堆)序列。
时间: 2024-06-13 10:08:36 浏览: 7
给定序列(67,45,87,19,55,32,70,60,90,23)的初始堆(大根堆)序列如下:
90, 67, 87, 60, 55, 32, 70, 19, 45, 23
堆是一种特殊的树形数据结构,它满足以下两个条件:
1. 堆是一个完全二叉树;
2. 堆中每个节点的值都大于等于(或小于等于)其子节点的值。
在初始堆序列中,我们可以看到90是最大的数,因此它是堆的根节点。接下来,我们将67和87与它们的父节点90比较,发现它们都比90小,因此它们不需要调整位置。然后,我们将60和55与它们的父节点67比较,发现它们都比67小,因此它们也不需要调整位置。接下来,我们将32和70与它们的父节点87比较,发现它们都比87小,因此它们也不需要调整位置。然后,我们将19和45与它们的父节点60比较,发现它们都比60小,因此它们也不需要调整位置。最后,我们将23与它的父节点55比较,发现它比55小,因此需要将23和55交换位置。这样,我们就得到了初始堆序列。
相关问题
给定序列(67,45,87,19,55,32,70,60,90,23),分别写出利用直接插入排序、冒泡排序、直接选择排序和二路归并排序每一趟的结果。
利用直接插入排序对给定序列进行排序的过程如下:
第一趟:(45,67,87,19,55,32,70,60,90,23)
第二趟:(45,67,87,19,55,32,70,60,90,23)
第三趟:(19,45,67,87,55,32,70,60,90,23)
第四趟:(19,45,55,67,87,32,70,60,90,23)
第五趟:(19,32,45,55,67,87,70,60,90,23)
第六趟:(19,32,45,55,67,70,87,60,90,23)
第七趟:(19,32,45,55,60,67,70,87,90,23)
第八趟:(19,23,32,45,55,60,67,70,87,90)
利用冒泡排序对给定序列进行排序的过程如下:
第一趟:(45,67,19,55,32,70,60,87,23,90)
第二趟:(45,19,55,32,67,60,70,23,87,90)
第三趟:(19,45,32,55,60,67,23,70,87,90)
第四趟:(19,32,45,55,60,23,67,70,87,90)
第五趟:(19,32,45,55,23,60,67,70,87,90)
第六趟:(19,32,45,23,55,60,67,70,87,90)
第七趟:(19,32,23,45,55,60,67,70,87,90)
第八趟:(19,23,32,45,55,60,67,70,87,90)
利用直接选择排序对给定序列进行排序的过程如下:
第一趟:(19,45,87,67,55,32,70,60,90,23)
第二趟:(19,23,87,67,55,32,70,60,90,45)
第三趟:(19,23,32,67,55,87,70,60,90,45)
第四趟:(19,23,32,45,55,87,70,60,90,67)
第五趟:(19,23,32,45,55,60,70,87,90,67)
第六趟:(19,23,32,45,55,60,67,87,90,70)
第七趟:(19,23,32,45,55,60,67,70,90,87)
第八趟:(19,23,32,45,55,60,67,70,87,90)
利用二路归并排序对给定序列进行排序的过程如下:
第一趟:(45,67,19,55,32,70,60,87,23,90)
第二趟:(19,45,55,67,32,60,70,87,23,90)
第三趟:(19,32,45,55,60,67,70,87,23,90)
第四趟:(19,23,32,45,55,60,67,70,87,90)
1、给定序列{63,90,55,58,45,42,67,83,70,10,32,16}(1)构造二叉排序树
首先,我们可以将序列中的第一个元素作为根节点插入二叉排序树中,然后从第二个元素开始遍历,将每个元素依次插入二叉排序树中,插入时需要按照二叉排序树的性质进行比较并找到合适的位置插入。
对于该序列,构造出的二叉排序树如下所示:
```
63
/ \
55 90
/ \ / \
45 58 67 83
/ / \
42 32 70
\
16
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)