Back to TILs

C++ heap

Date: 2023-04-05Last modified: 2023-12-22

Table of contents

Introduction

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

Operations

Types

Indexes

Pi=i12 Li=2×i+1 Ri=2×i+2
Max heap in tree representation and squashed on array.
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);

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