阿摩線上測驗 登入

申論題資訊

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

題組內容

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

申論題內容

(三)把上題所產生的最大堆積樹刪除最大元素,其更新完的結果為何? (15分)

詳解 (共 2 筆)

詳解 提供者:努力加油
#include <stdio.h>
int arr[100] = {12, 10, 7, 23, 13, 6, 15, 17, 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 < 9; i++) {
        printf("\n%d\n", a[i]);
    }
}
int main() {
    
    // 呼叫 kk 函數來排序並印出前10個元素
    kk(arr, 10);
    return 0;}            
tree:  
                        23   - > root node 
            17                    12
     15           13       10
3        6    7
詳解 提供者:hchungw

在最大堆積樹中刪除最大元素(即堆頂元素)後,通常採用以下步驟來更新堆,以確保其繼續滿足最大堆的性質:
移除堆頂元素:首先移除根節點(即最大元素),通常是將堆中最後一個元素移至根節點位置,以保持完全二叉樹的結構。
下沉調整(Heapify Down):將新的根節點與其子節點比較,如果它小於它的一個或兩個子節點,就將它與最大的子節點交換。重複這個過程,直到當前節點大於它的子節點或者它已經是葉節點。
給定的最大堆積樹為:
46
,
17
,
23
,
13
,
12
,
6
,
7
,
10
,
15
,
3
46,17,23,13,12,6,7,10,15,3
刪除最大元素(46)後,並將最後一個元素(3)移動到根節點的過程如下:
刪除46,將3移至根節點:
3
,
17
,
23
,
13
,
12
,
6
,
7
,
10
,
15
3,17,23,13,12,6,7,10,15
由於3小於其子節點17和23,我們需要進行下沉調整。3與最大的子節點23交換:
23
,
17
,
3
,
13
,
12
,
6
,
7
,
10
,
15
23,17,3,13,12,6,7,10,15
接下來,3還需要與其子節點進行比較。由於3沒有子節點比它大,所以這一步可以省略。
最終更新完的最大堆積樹為:
23
,
17
,
3
,
13
,
12
,
6
,
7
,
10
,
15
23,17,3,13,12,6,7,10,15
這樣,我們就完成了刪除最大堆積樹中的最大元素並進行了必要的調整,以確保結果仍然是一個最大堆。