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

Binary Heap là cây nhị phân hoàn chỉnh (complete binary tree) 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 min_heap():

Bắt đầu
  Khai báo hàm min_heap(int *a, int m, int n)
    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_minheap:

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

Ví dụ

#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 << "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_minheap(a, n);
    cout << "Min 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
Min Heap
1
4
2
6
7