Heap trong C++ STL: make_heap, push_heap, pop_heap, sort_heap, is_heap

Giới thiệu các hàm heap trong C++ STL: make_heap, push_heap, pop_heap, sort_heap, is_heap, is_heap_until. Heap trong C++ mặc định là max-heap (phần tử lớn nhất ở đầu).

make_heap() và front()

Chuyển vùng nhớ thành heap, front() trả về phần tử lớn nhất.

#include 
using namespace std;
int main() {
    vector heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());
    cout << "Top element is : " << heap.front() << endl;
}

Kết quả: Top element is : 53

push_heap() và pop_heap()

push_heap cân bằng lại sau khi thêm phần tử (push_back trước). pop_heap cân bằng sau khi xóa phần tử lớn nhất (phần tử lớn nhất được chuyển về cuối, sau đó pop_back).

#include 
using namespace std;
int main() {
    vector heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());
    cout << "Top element is : " << heap.front() << endl;
    heap.push_back(60);
    push_heap(heap.begin(), heap.end());
    cout << "Top element after insert : " << heap.front() << endl;
    pop_heap(heap.begin(), heap.end());
    heap.pop_back();
    cout << "Top element after deletion : " << heap.front() << endl;
}

Kết quả: 53 → 60 → 53

sort_heap()

Sắp xếp heap tăng dần (heap sort).

#include 
using namespace std;
int main() {
    vector heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());
    cout << "Before Sort : ";
    for (const auto &i : heap) cout << i << ' ';
    sort_heap(heap.begin(), heap.end());
    cout << "\nAfter Sort : ";
    for (const auto &i : heap) cout << i << ' ';
}

Kết quả: Before: 53 43 33 38 28 → After: 28 33 38 43 53

is_heap() và is_heap_until()

is_heap kiểm tra container có phải heap. is_heap_until trả về iterator đến vị trí cuối cùng vẫn là heap.

#include 
using namespace std;
int main() {
    vector heap = {33, 43, 53, 38, 28};
    vector::iterator iter;
    is_heap(heap.begin(), heap.end()) ? cout << "The is a heap " : cout << "The is not a heap";
    cout << endl;
    cout << "Heapify" << endl;
    make_heap(heap.begin(), heap.end());
    is_heap(heap.begin(), heap.end()) ? cout << "The is a heap " : cout << "The is not a heap";
    cout << endl;
    vector::iterator iter2 = is_heap_until(heap.begin(), heap.end());
    cout << "The heap elements are : ";
    for (iter=heap.begin(); iter!=iter2; iter++)
        cout << *iter << " ";
}

Kết quả: Not heap → Heapify → Is heap → Elements: 53 43 33 38 28