a binary tree inside an array, so it does not use parent/child pointers. - heap / std::make_heap

Key Properties

• find min in $O(1)$
• insert in $O(ln N)$
• delete min in $O(ln N)$
• But search is $O(N)$
• make_heap is $O(N)$
• sort heap is still $O(N ln N)$

Common uses for heap

• To build priority queues.
• To support heap sorts.
• To compute the nth minimum (or maximum) element(s) of a collection quickly.
• To impress your non-programmer friends.

There are two kinds of heaps: a max-heap and a min-heap which are different by the order in which they store the tree nodes.

In a max-heap, parent nodes have a greater value than each of their children. In a min-heap, every parent node has a smaller value than its child nodes. This is called the “heap property”, and it is true for every single node in the tree.

A sorted array from low-to-high is a valid min-heap.

see also

• Beating std::sort - Andrei
• Finding the first n largest elements in an array
• Fibonacci heap - has a better amortized running time than many other priority queue data structures.
• Geometric Search Trees - define zip tree as well
• How can building a heap be O(n) time complexity?

As C++ Algorithm

make_heap
push_heap
pop_heap

#include <algorithm>
#include <iostream>
#include <string_view>
#include <type_traits>
#include <vector>
 
void println(std::string_view rem, const auto& v)
{
    std::cout << rem;
    if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>)
        std::cout << v;
    else
        for (int e : v)
            std::cout << e << ' ';
    std::cout << '\n';
}
 
int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9};
 
    std::make_heap(v.begin(), v.end());
    println("after make_heap: ", v);
 
    std::pop_heap(v.begin(), v.end()); // moves the largest to the end
    println("after pop_heap:  ", v);
 
    int largest = v.back();
    println("largest element: ", largest);
 
    v.pop_back(); // actually removes the largest element
    println("after pop_back:  ", v);
}

input:           3 1 4 1 5 9
after make_heap: 9 5 4 1 1 3
after pop_heap:  5 3 4 1 1 9
largest element: 9
after pop_back:  5 3 4 1 1