Algoteka

Heap - Using the STL priority_queue

Specification

A heap class from the C++ Standard Template Library providing $O(\log n)$ insertion and $O(\log n)$ deletion.

Code

```c++
#include <queue>

int main() {
    std::priority_queue<int> heap;
    heap.push(5);
    int max_element = heap.top();
    heap.pop();
}
```

Further reading

[Heap Data Structures - tutorialspoint.com](https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm)
[Chapter 6.1: Heaps - Introduction to Algorithms, Third Edition (Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein)](https://sd.blackball.lv/library/Introduction_to_Algorithms_Third_Edition_%282009%29.pdf#%5B%7B%22num%22:513,%22gen%22:0%7D,%7B%22name%22:%22Fit%22%7D%5D)

References

{
    "classes":
    [
        {
            "name" : "std::priority_queue",
            "urls" : ["https://en.cppreference.com/w/cpp/container/priority_queue", "https://cplusplus.com/reference/queue/priority_queue/"]
        }
    ],
    "functions":
    [
        {
            "name" : "std::priority_queue::push",
            "urls" : ["https://en.cppreference.com/w/cpp/container/priority_queue/push", "https://cplusplus.com/reference/queue/priority_queue/push/"]
        },
        {
            "name" : "std::priority_queue::top",
            "urls" : ["https://en.cppreference.com/w/cpp/container/priority_queue/top", "https://cplusplus.com/reference/queue/priority_queue/top/"]
        },
        {
            "name" : "std::priority_queue::pop",
            "urls" : ["https://en.cppreference.com/w/cpp/container/priority_queue/pop", "https://cplusplus.com/reference/queue/priority_queue/pop/"]
        }
    ]
}

Problem Description

Implement a max-heap data structure. Insert an element into it, then fetch the maximum element, then delete said maximum element.