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

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

อัลกอริทึม

สำหรับ max_heap:

เริ่มต้น
  ประกาศฟังก์ชัน max_heap()
  ประกาศ 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_maxheap:

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

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

#include <iostream>
using namespace std;

void max_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_maxheap(int *a, int n) {
    int k;
    for (k = n/2; k >= 1; k--) {
        max_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 elements " << i << endl;
        cin >> a[i];
    }
    build_maxheap(a, n);
    cout << "Max Heap\n";
    for (i = 1; i <= n; i++) {
        cout << a[i] << endl;
    }
}

ผลลัพธ์

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