國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

四、二元堆積 (Binary Heap) 是一種優先佇列 (Priority Queue)，主要用來管理具有優先權順序的資料物件，每個資料物件具有一個可以界定大小或前後順序的鍵值 (Key)，我們在此假設鍵值越低的資料物件有越高的優先權。

    (一)請完整描述最小堆積 (Min_Heap) 的定義與相關的操作功能。（5分）

    (二)請說明堆積排序 (Heap Sort) 的方法並分析其時間複雜度。（5分）

    (三)若有兩個二元樹 T₁ 及 T₂，其節點具有堆積特性且高度分別是 O(log n)與 O(log m)，請提供一個方法將此兩個二元樹結合成為一個節點具有堆積特性的二元樹 T，此方法的時間須為 O(logn+logm)。（10分）

#include <iostream>

using namespace std;

/* 交換 a 和 b 兩值 */

void swap(int* a, int* b) {

    int tmp = *a;

    *a = *b;

    *b = tmp;

}

/* Heapify 是指將子樹序列修正至符合 heap ordering 的序列 */

void maxHeapify(int arr[ ], int N, int idx) {

    if (idx >= N) {

        return;

    }

    int l = 2*idx+1; // 左兒子

    int r = 2*idx+2; // 右兒子

    int max = idx;

    // 找出最大值的節點和它的兒子

    if (l < N && arr[l] > arr[idx]) {

        max = l;

    }

    if (r < N && arr[r] > arr[max]) {

        max = r;

    }

    if (max != idx) {

        swap(&arr[max], &arr[idx]);

        maxHeapify(arr, N, max); // 遞迴呼叫

    }

}

/* 由下而上做最大堆積 */

void buildMaxHeap(int arr[ ], int N) {

    for (int i = N/2-1; i >= 0; i--) {

        maxHeapify(arr, N, i);

    }

}

/* 合併 a 和 b 堆積樹 */

void mergeHeaps(int merged[ ], int a[ ], int b[ ], int N, int M) {

    for (int i = 0; i < N; i++) {

        merged[i] = a[i];

    }

    for (int i = 0;i < M; i++) {

        merged[N+i] = b[i];

    }

    buildMaxHeap(merged, N+M);

}

int main( ) {

    int a[ ] = {10, 5, 6, 2};

    int b[ ] = {12, 7, 9};

    const int N = sizeof(a)/sizeof(a[0]);

    const int M = sizeof(b)/sizeof(b[0]);

    int merged[N+M];

    mergeHeaps(merged, a, b, N, M);

    for (int i = 0; i < N + M; i++) {

        printf("%d ", merged[i]);

    }

    return 0;

}