将关键字序列1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16, 17,18, 19,20建成最大堆,画出该最大堆对应的二叉树。
时间: 2023-11-14 09:08:00 浏览: 44
以下是关键字序列1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20所对应的最大堆二叉树:
```
20
/ \
19 18
/ \ / \
17 16 15 14
/ \ / \ / \ / \
13 12 11 10 9 8 7 6
/ \
5 4
/ \
3 2
/
1
```
相关问题
对关键字序列4,2,8,5,7,6,1,3,10,9,做两路归并排序
可以的,这是一个关于算法的问题。以下是关键字序列4,2,8,5,7,6,1,3,10,9的两路归并排序过程:
1. 将序列平均分成两个子序列:4,2,8,5,7 和 6,1,3,10,9
2. 对左子序列4,2,8,5,7进行递归排序,步骤同下:
1. 将子序列平均分成两个子序列:4,2 和 8,5,7
2. 对左子序列4,2进行递归排序,得到子序列2,4
3. 对右子序列8,5,7进行递归排序,得到子序列5,7,8
4. 将两个子序列2,4 和 5,7,8进行归并排序,得到子序列2,4,5,7,8
3. 对右子序列6,1,3,10,9进行递归排序,步骤同2
4. 将两个子序列2,4,5,7,8和1,3,6,9,10进行归并排序,得到完整的序列1,2,3,4,5,6,7,8,9,10
以上就是关键字序列4,2,8,5,7,6,1,3,10,9的两路归并排序过程。
对关键字序列10,9,8,7,6,5,4,3,2,1,做两路归并排序
我可以回答您的问题。
首先,要将关键字序列10,9,8,7,6,5,4,3,2,1拆分为两个子序列,分别为10,9,8,7,6和5,4,3,2,1。
然后,对这两个子序列递归地进行归并排序,直到每个子序列只剩下一个元素。
最后,将这两个子序列按照归并排序的规则进行合并,得到完整的排序结果。
代码实现如下:
```
void merge(int arr[], int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right)
{
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main()
{
int arr[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.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)