申論題 - 阿摩線上測驗

申論題資訊

試卷：112年 - 112 普通考試_統計、資訊處理：資料處理概要#115737
科目：資料處理
年份：112年
排序：0

題組內容

二、有一筆資料為12，10，7，23，13，6，15，17，46，3。

申論題內容

(二)請依序建置最大堆積（Max heap）樹（由上而下Top Down建置）。（10分）

詳解 (共 2 筆)

詳解提供者：努力加油

#include <stdio.h>
int arr[100] = {12, 10, 7, 23, 13, 6, 15, 17, 46, 3};
void kk(int a[], int size) {
// 完整的冒泡排序, 由大到小排序。
for (int j = 0; j < size - 1; j++) {
for (int i = 0; i < size - 1 - j; i++) {
if (a[i + 1] > a[i]) {
int temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
// 印出前10個元素
for (int i = 0; i < 10; i++) {
printf("\n%d\n", a[i]);
}
}
int main() {

// 呼叫 kk 函數來排序並印出前10個元素
kk(arr, 10);
return 0;
}

tree:

46 - > root node

17 23

15 13 12 10

3 6 7

詳解提供者：hchungw

建置最大堆积（Max Heap）树的过程与建置最小堆积树类似，但是要保证每个父节点的值大于其子节点的值。我们将按照给定的数据序列逐一插入元素到堆中，并在每次插入后通过上浮（percolate up）操作确保堆的性质得以维护。

给定数据序列为：12, 10, 7, 23, 13, 6, 15, 17, 46, 3。

下面是依序插入过程中，最大堆积树的变化：

插入12：
12
12
插入10：
12
,
10
12,10
插入7：
12
,
10
,
7
12,10,7
插入23：
23
,
12
,
7
,
10
23,12,7,10
插入13：
23
,
13
,
7
,
10
,
12
23,13,7,10,12
插入6：
23
,
13
,
7
,
10
,
12
,
6
23,13,7,10,12,6
插入15：
23
,
13
,
15
,
10
,
12
,
6
,
7
23,13,15,10,12,6,7
插入17：
23
,
17
,
15
,
13
,
12
,
6
,
7
,
10
23,17,15,13,12,6,7,10
插入46：
46
,
17
,
23
,
13
,
12
,
6
,
7
,
10
,
15
46,17,23,13,12,6,7,10,15
插入3：
46
,
17
,
23
,
13
,
12
,
6
,
7
,
10
,
15
,
3
46,17,23,13,12,6,7,10,15,3
在每次插入操作之后，我们通过比较新插入节点与其父节点的值，并在必要时进行交换，以确保每个父节点的值都大于其子节点的值。这样，我们就得到了满足最大堆性质的堆积树。

最终的最大堆积树的数组表示如下：
46
,
17
,
23
,
13
,
12
,
6
,
7
,
10
,
15
,
3
46,17,23,13,12,6,7,10,15,3

这表示根节点是最大的元素，每个父节点的值都大于或等于其子节点的值，满足最大堆的性质。