Chương trình C++ triển khai Max Heap

Binary Heap là cây nhị phân hoàn chỉnh là Min Heap hoặc Max Heap. Trong Max Binary Heap, khóa tại root phải lớn nhất trong tất cả khóa trong Heap. Tính chất này phải đúng đệ quy cho mọi nút. Min Binary Heap tương tự Min Heap.

Thuật toán

Hàm max_heap:

Bắt đầu
  Khai báo hàm max_heap()
    Khai báo j, t kiểu integer.
    Khởi tạo t = a[m].
    j = 2 * m.
    while (j <= n) do
      if (j < n && a[j+1] > a[j]) thì j = j + 1
      if (t > a[j]) thì break
      else if (t <= a[j]) thì
        a[j / 2] = a[j]
        j = 2 * j
    a[j/2] = t
    Trả về
Kết thúc.

Hàm build_maxheap:

Bắt đầu
  Khai báo hàm build_maxheap(int *a, int n).
    Khai báo k kiểu integer.
    for(k = n/2; k >= 1; k--)
      Gọi max_heap(a, k, n)
Kết thúc.

Ví dụ

#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 << "Nhập số phần tử mảng\n";
    cin >> n;
    int a[30];
    for (i = 1; i <= n; i++) {
        cout << "Nhập phần tử " << i << endl;
        cin >> a[i];
    }
    build_maxheap(a, n);
    cout << "Max Heap\n";
    for (i = 1; i <= n; i++) {
        cout << a[i] << endl;
    }
}

Kết quả

Nhập số phần tử mảng 5
Nhập phần tử 1 7
Nhập phần tử 2 6
Nhập phần tử 3 2
Nhập phần tử 4 1
Nhập phần tử 5 4
Max Heap
7
6
2
1
4