โปรแกรม C++ เรียงลำดับอาร์เรย์ 10 ค่าด้วย Heap Sort

Heap Sort เป็นอัลกอริทึมการเรียงลำดับที่พัฒนาจากโครงสร้างข้อมูล Binary Heap ใน Max Heap โหนดลูกจะมีค่าน้อยกว่าหรือเท่ากับโหนดพาเรนต์ ส่วน Min Heap โหนดลูกจะมีค่ามากกว่าหรือเท่ากับโหนดพาเรนต์

ตัวอย่างขั้นตอนการทำงานของ Heap Sort ดังนี้

อาร์เรย์ต้นฉบับ 10 ค่าก่อนเรียงลำดับ:

สร้าง Binary Max Heap ด้วยฟังก์ชัน max-heapify เขียนในรูปอาร์เรย์ได้ดังนี้:

นำโหนดราก (ค่าสูงสุด) วางไว้ท้ายอาร์เรย์ แล้วเรียก max-heapify อีกครั้งกับส่วนที่เหลือ ทำซ้ำจนได้อาร์เรย์ที่เรียงลำดับแล้ว:

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

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int temp;
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i) {
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    int temp;
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i >= 0; i--) {
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {20, 7, 1, 54, 10, 15, 90, 23, 77, 25};
    int n = 10;
    int i;
    cout << "Given array is: " << endl;
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    heapSort(arr, n);
    printf("\nSorted array is: \n");
    for (i = 0; i < n; ++i)
        cout << arr[i] << " ";
}

ผลลัพธ์

Given array is: 20 7 1 54 10 15 90 23 77 25
Sorted array is: 1 7 10 15 20 23 25 54 77 90

ในโปรแกรมนี้ ฟังก์ชัน heapify() ใช้แปลงข้อมูลเป็น Heap เป็นฟังก์ชันแบบเรียกซ้ำ (recursive) สร้าง Max Heap เริ่มจากโหนดที่เรียกใช้ คือ index i

void heapify(int arr[], int n, int i) {
    int temp;
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i) {
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

ฟังก์ชัน heapSort() เรียงลำดับอาร์เรย์ด้วย Heap Sort เริ่มจากโหนดที่ไม่ใช่ leaf เรียก heapify() ทุกโหนด แปลงอาร์เรย์เป็น Binary Max Heap:

for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);

จากนั้น heapSort() นำโหนดรากไปวางท้ายอาร์เรย์ในแต่ละรอบ แล้วเรียก heapify() เพื่อให้ส่วนที่เหลือเป็น Max Heap ทำซ้ำจนได้อาร์เรย์เรียงลำดับ:

for (int i = n - 1; i >= 0; i--) {
    temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
}

ใน main() แสดงอาร์เรย์ต้นฉบับ เรียก heapSort() แล้วแสดงผลลัพธ์:

cout<<"Given array is: "<<endl;
for (i = 0; i < n; i++) cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i) cout<<arr[i]<<" ";