โปรแกรม C++ Implement Min Heap

Binary Heap เป็น complete binary tree ที่เป็น Min Heap หรือ Max Heap ใน Max Binary Heap key ที่ root ต้องมากที่สุดของทุก key ใน Binary Heap คุณสมบัตินี้ต้องเป็นจริงแบบ recursive สำหรับทุกโหนดใน Binary Tree Min Binary Heap คล้ายกับ Min Heap

อัลกอริทึม

สำหรับ min_heap():

เริ่มต้น
  ประกาศฟังก์ชัน min_heap(int *a, int m, int n)
  ประกาศ j, t เป็น integer
  กำหนด t = a[m]
  j = 2 * m
  while (j <= n) ทำ
    if (j < n && a[j+1] < a[j]) แล้ว j = j + 1
    if (t < a[j]) แล้ว break
    else if (t >= a[j]) แล้ว a[j/2] = a[j], j = 2 * j
  a[j/2] = t
  คืนค่า
สิ้นสุด

สำหรับ build_minheap:

เริ่มต้น
  ประกาศฟังก์ชัน build_minheap(int *a, int n)
  ประกาศ k เป็น integer
  for(k = n/2; k >= 1; k--) เรียก min_heap(a, k, n)
สิ้นสุด

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

#include <iostream>
using namespace std;

void min_heap(int *a, int m, int n) {
    int j, t;
    t = a[m];
    j = 2 * m;
    while (j <= n) {
        if (j < n && a[j+1] < a[j])
            j = j + 1;
        if (t < a[j])
            break;
        else if (t >= a[j]) {
            a[j/2] = a[j];
            j = 2 * j;
        }
    }
    a[j/2] = t;
    return;
}

void build_minheap(int *a, int n) {
    int k;
    for (k = n/2; k >= 1; k--) {
        min_heap(a, k, n);
    }
}

int main() {
    int n, i;
    cout << "enter no of elements of array\n";
    cin >> n;
    int a[30];
    for (i = 1; i <= n; i++) {
        cout << "enter element " << i << endl;
        cin >> a[i];
    }
    build_minheap(a, n);
    cout << "Min Heap\n";
    for (i = 1; i <= n; i++) {
        cout << a[i] << endl;
    }
}

ผลลัพธ์

enter no of elements of array 5
enter element 1 7
enter element 2 6
enter element 3 2
enter element 4 1
enter element 5 4
Min Heap
1
4
2
6
7