C++ heap

Photo by Markus Spiske on Unsplash

Table of contents

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

• Left child of i

• Right child of i

  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);

Draw heap from https://en.cppreference.com/w/cpp/algorithm/ranges/make_heap

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 

References

• CppCon 2018: Jonathan Boccara “105 STL Algorithms in Less Than an Hour”
• Heap Data Structure