แปลง Min Heap เป็น Max Heap ใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมที่แปลง Min Heap เป็น Max Heap

เราจะได้รับการแสดงผลแบบอาร์เรย์ของ Min Heap มา ภารกิจคือแปลง Min Heap ที่ให้มาเป็น Max Heap โดยมีความซับซ้อนของเวลา O(n)

ตัวอย่างโค้ด

#include<bits/stdc++.h>
using namespace std;

// แปลง subtree ที่กำหนดให้เป็น heap
void convert_arrayheap(int arr[], int i, int n) {
    int l = 2*i + 1;
    int r = 2*i + 2;
    int largest = i;
    if (l < n && arr[l] > arr[i])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        convert_arrayheap(arr, largest, n);
    }
}

// สร้าง Max Heap ให้สมบูรณ์
void convert_maxheap(int arr[], int n) {
    // heapify ทุกโหนด
    for (int i = (n-2)/2; i >= 0; --i)
        convert_arrayheap(arr, i, n);
}

// พิมพ์อาร์เรย์
void printArray(int* arr, int size) {
    for (int i = 0; i < size; ++i)
        printf("%d ", arr[i]);
}

int main() {
    int arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Min Heap array : ");
    printArray(arr, n);
    convert_maxheap(arr, n);
    printf("\nMax Heap array : ");
    printArray(arr, n);
    return 0;
}

ผลลัพธ์

Min Heap array : 3 5 9 6 8 20 10 12 18 9
Max Heap array : 20 18 10 12 9 9 3 5 6 8

คำอธิบาย

อัลกอริทึมใช้เทคนิค Heapify แบบ Bottom-up เริ่มจากโหนดพ่อระดับล่างสุด (index = (n-2)/2) และทำงานขึ้นมาจนถึงราก

ฟังก์ชัน convert_arrayheap() เปรียบเทียบโหนดปัจจุบันกับลูกซ้ายและลูกขวา หากลูกมีค่ามากกว่า จะสลับตำแหน่งและเรียกฟังก์ชันซ้ำ (Recursive) เพื่อให้ Subtree นั้นเป็น Max Heap

วิธีนี้มีความซับซ้อนของเวลา O(n) ซึ่งมีประสิทธิภาพมากกว่าการ Insert ทีละตัวที่ใช้เวลา O(n log n)