Chương trình C++ triển khai Binary 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.

Mô tả hàm:

• void BHeap::Insert(int ele): Chèn phần tử vào heap.
• void BHeap::DeleteMin(): Xóa phần tử nhỏ nhất từ heap.
• int BHeap::ExtractMin(): Lấy phần tử nhỏ nhất từ heap.
• void BHeap::showHeap(): Hiển thị các phần tử heap.
• void BHeap::heapifyup(int in): Duy trì cấu trúc heap bottom-up.
• void BHeap::heapifydown(int in): Duy trì cấu trúc heap top-down.

Ví dụ

#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;

class BHeap {
private:
    vector<int> heap;
    int l(int parent);
    int r(int parent);
    int par(int child);
    void heapifyup(int index);
    void heapifydown(int index);
public:
    BHeap() {}
    void Insert(int element);
    void DeleteMin();
    int ExtractMin();
    void showHeap();
    int Size();
};

int main() {
    BHeap h;
    while (1) {
        cout << "1.Chèn phần tử" << endl;
        cout << "2.Xóa phần tử nhỏ nhất" << endl;
        cout << "3.Lấy phần tử nhỏ nhất" << endl;
        cout << "4.Hiển thị Heap" << endl;
        cout << "5.Thoát" << endl;
        int c, e;
        cout << "Nhập lựa chọn: ";
        cin >> c;
        switch(c) {
            case 1:
                cout << "Nhập phần tử cần chèn: ";
                cin >> e;
                h.Insert(e);
                break;
            case 2:
                h.DeleteMin();
                break;
            case 3:
                if (h.ExtractMin() == -1) {
                    cout << "Heap rỗng" << endl;
                } else
                    cout << "Phần tử nhỏ nhất: " << h.ExtractMin() << endl;
                break;
            case 4:
                cout << "Các phần tử Heap: ";
                h.showHeap();
                break;
            case 5:
                exit(1);
                default:
                cout << "Lựa chọn đúng" << endl;
        }
    }
    return 0;
}

int BHeap::Size() { return heap.size(); }

void BHeap::Insert(int ele) {
    heap.push_back(ele);
    heapifyup(heap.size() - 1);
}

void BHeap::DeleteMin() {
    if (heap.size() == 0) {
        cout << "Heap rỗng" << endl;
        return;
    }
    heap[0] = heap.at(heap.size() - 1);
    heap.pop_back();
    heapifydown(0);
    cout << "Đã xóa phần tử" << endl;
}

int BHeap::ExtractMin() {
    if (heap.size() == 0) return -1;
    else return heap.front();
}

void BHeap::showHeap() {
    vector<int>::iterator pos = heap.begin();
    cout << "Heap --> ";
    while (pos != heap.end()) {
        cout << *pos << " ";
        pos++;
    }
    cout << endl;
}

int BHeap::l(int parent) {
    int l = 2 * parent + 1;
    if (l < heap.size()) return l;
    else return -1;
}

int BHeap::r(int parent) {
    int r = 2 * parent + 2;
    if (r < heap.size()) return r;
    else return -1;
}

int BHeap::par(int child) {
    int p = (child - 1) / 2;
    if (child == 0) return -1;
    else return p;
}

void BHeap::heapifyup(int in) {
    if (in >= 0 && par(in) >= 0 && heap[par(in)] > heap[in]) {
        int temp = heap[in];
        heap[in] = heap[par(in)];
        heap[par(in)] = temp;
        heapifyup(par(in));
    }
}

void BHeap::heapifydown(int in) {
    int child = l(in);
    int child1 = r(in);
    if (child >= 0 && child1 >= 0 && heap[child] > heap[child1]) {
        child = child1;
    }
    if (child > 0 && heap[in] > heap[child]) {
        int t = heap[in];
        heap[in] = heap[child];
        heap[child] = t;
        heapifydown(child);
    }
}

Kết quả

1.Chèn phần tử 2.Xóa phần tử nhỏ nhất 3.Lấy phần tử nhỏ nhất 4.Hiển thị Heap 5.Thoát
Nhập lựa chọn: 1
Nhập phần tử cần chèn: 2
...
Hiển thị các phần tử Heap: Heap --> 2 3 7 6
...
Phần tử nhỏ nhất: 2
...
Đã xóa phần tử
Hiển thị các phần tử Heap: Heap --> 3 6 7