Back to TILs

# C++ heap ## Introduction

A Heap is a special Tree-based data structure in which the tree is a complete binary tree.

## Operations

• Heapify: a process of creating a heap from an array.
• Insertion: process to insert an element in existing heap time complexity O(log N).
• Deletion: deleting the top element of the heap or the highest priority element, and then organizing the heap and returning the element with time complexity O(log N).
• Peek: to check or find the most prior element in the heap, (max or min element for max and min heap).

## Types

• max heap
• the key present at the root node must be greatest among the keys present at all of it’s children
• the same property must be recursively true for all sub-trees in that Binary Tree.
• min heap
• the key present at the root node must be minimum among the keys present at all of it’s children
• the same property must be recursively true for all sub-trees in that Binary Tree.
• binomial heap
• fibonacci heap
• leftist heap
• k-ary heap

## Indexes

• Parent of i
${P}_{i}=\frac{i-1}{2}$
• Left child of i
${L}_{i}=2×i+1$
• Right child of i
${R}_{i}=2×i+2$ Fig. 1 - Max heap in tree representation and squashed on array.
  auto print = [](auto label, auto numbers) {
fmt::print("{:20} ", label);
for (const auto& number : numbers) {
fmt::print("{} ", number);
}
if (std::ranges::is_heap(numbers)) {
fmt::print(" IS HEAP");
} else {
fmt::print(" IS NOT HEAP");
}
fmt::print("\n");
};

  // Input
std::vector<int> numbers{1, 2, 3, 4, 5, 6, 7, 8, 9};
print("numbers", numbers);

// Construct max heap
std::make_heap(begin(numbers), end(numbers));
std::ranges::make_heap(numbers);
print("make_heap max", numbers);
draw_heap(numbers);

// Pop
std::pop_heap(begin(numbers), end(numbers));
print("pop_heap", numbers);
auto n = numbers.back();
numbers.pop_back();
draw_heap(numbers);

// Push
n = 42;
print("numbers.pop_back", numbers);
numbers.push_back(n);
print("numbers.push_back", numbers);
std::push_heap(begin(numbers), end(numbers));
print("push_heap", numbers);
draw_heap(numbers);

// Construct min heap
std::make_heap(begin(numbers), end(numbers), std::greater<>{});
print("make_heap min", numbers);
draw_heap(numbers);

void draw_heap(auto const& v) {
auto bails = [](int n, int w) {
auto b = [](int w) {
out("┌"), out("─", w), out("┴"), out("─", w), out("┐");
};
if (!(n /= 2)) return;
for (out(' ', w); n-- > 0;) b(w), out(' ', w + w + 1);
out('\n');
};
auto data = [](int n, int w, auto& first, auto last) {
for (out(' ', w); n-- > 0 && first != last; ++first)
out(*first), out(' ', w + w + 1);
out('\n');
};
auto tier = [&](int t, int m, auto& first, auto last) {
const int n{1 << t};
const int w{(1 << (m - t - 1)) - 1};
bails(n, w), data(n, w, first, last);
};
const int m{static_cast<int>(std::ceil(std::log2(1 + v.size())))};
auto first{v.cbegin()};
for (int i{}; i != m; ++i) {
tier(i, m, first, v.cend());
}
}


## Possible output

numbers              1 2 3 4 5 6 7 8 9  IS NOT HEAP
make_heap max        9 8 7 4 5 6 3 2 1  IS HEAP
9
┌───┴───┐
8       7
┌─┴─┐   ┌─┴─┐
4   5   6   3
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
2 1
pop_heap             8 5 7 4 1 6 3 2 9  IS NOT HEAP
8
┌───┴───┐
5       7
┌─┴─┐   ┌─┴─┐
4   1   6   3
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
2
numbers.pop_back     8 5 7 4 1 6 3 2  IS HEAP
numbers.push_back    8 5 7 4 1 6 3 2 42  IS NOT HEAP
push_heap            42 8 7 5 1 6 3 2 4  IS HEAP
42
┌───┴───┐
8       7
┌─┴─┐   ┌─┴─┐
5   1   6   3
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
2 4
make_heap min        1 2 3 4 8 6 7 5 42  IS NOT HEAP
1
┌───┴───┐
2       3
┌─┴─┐   ┌─┴─┐
4   8   6   7
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
5 42