Một Heap (Đống) là một cây nhị phân hoàn chỉnh (complete binary tree) là Min Heap hoặc Max Heap. Trong Max Heap, khóa tại gốc phải lớn nhất trong tất cả các khóa có mặt trong Heap. Tính chất này phải đúng đệ quy cho tất cả các nút trong Cây Nhị phân đó. Min Heap tương tự như Max Heap.
Mô tả các hàm
void BHeap::Insert(int ele): Thực hiện chèn phần tử vào heap.
void BHeap::DeleteMin(): Thực hiện xóa giá trị nhỏ nhất khỏi heap.
int BHeap::ExtractMin(): Thực hiện trích xuất giá trị nhỏ nhất từ heap.
void BHeap::showHeap(): Hiển thị các phần tử của heap.
void BHeap::heapifyup(int in): Duy trì cấu trúc heap theo cách bottom-up.
void BHeap::heapifydown(int in): Duy trì cấu trúc heap theo cách top-down.
Mã 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 in);
void heapifydown(int in);
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.Trích xuất 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 << "Hiển thị các phần tử của Heap: ";
h.showHeap();
break;
case 5:
exit(1);
default:
cout << "Nhập 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ả đầu ra
1.Chèn phần tử 2.Xóa phần tử nhỏ nhất 3.Trích xuất 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 1.Chèn phần tử 2.Xóa phần tử nhỏ nhất 3.Trích xuất 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: 3 1.Chèn phần tử 2.Xóa phần tử nhỏ nhất 3.Trích xuất 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: 7 1.Chèn phần tử 2.Xóa phần tử nhỏ nhất 3.Trích xuất 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: 6 1.Chèn phần tử 2.Xóa phần tử nhỏ nhất 3.Trích xuất phần tử nhỏ nhất 4.Hiển thị Heap 5.Thoát Nhập lựa chọn: 4 Hiển thị các phần tử của Heap: Heap --> 2 3 7 6 1.Chèn phần tử 2.Xóa phần tử nhỏ nhất 3.Trích xuất phần tử nhỏ nhất 4.Hiển thị Heap 5.Thoát Nhập lựa chọn: 3 Phần tử nhỏ nhất: 2 1.Chèn phần tử 2.Xóa phần tử nhỏ nhất 3.Trích xuất phần tử nhỏ nhất 4.Hiển thị Heap 5.Thoát Nhập lựa chọn: 3 Phần tử nhỏ nhất: 2 1.Chèn phần tử 2.Xóa phần tử nhỏ nhất 3.Trích xuất phần tử nhỏ nhất 4.Hiển thị Heap 5.Thoát Nhập lựa chọn: 2 Đã xóa phần tử 1.Chèn phần tử 2.Xóa phần tử nhỏ nhất 3.Trích xuất phần tử nhỏ nhất 4.Hiển thị Heap 5.Thoát Nhập lựa chọn: 4 Hiển thị các phần tử của Heap: Heap --> 3 6 7 1.Chèn phần tử 2.Xóa phần tử nhỏ nhất 3.Trích xuất phần tử nhỏ nhất 4.Hiển thị Heap 5.Thoát Nhập lựa chọn: 5