DTL

Heap

Go back

Introduction

Heap data structure is a complete binary tree that satisfies the heap property, where any given node is always greater or smaller than its child node(s) and the key of the root node is the largest or smallest among all other node (max heap or min heap).

Advantages

  • Used in the implementation of priority queues.
  • Allows us to sort the elements (Heap sort).
  • Useful when trying to apply Prim's or Dijkstra's algorithm.

Disadvantages

  • Limited number of methods.

Using heap with DTL

#include "heap.hpp"
#include "vector.hpp"
#include <iostream>

int main() {
  dby::vector<int> vec = { 3, 0, 9, 6, 2, 8, 1, 7, 4, 5 };

  // Create heap from vector
  dby::Heap::make_heap(vec);
  
  while (vec.size()) {
    std::cout << "FRONT: " << vec.front() << '\n';
    // Remove top element of the heap
    dby::Heap::pop_heap(vec);
  }

  // Inserts elements into the heap
  dby::Heap::push_heap(vec, 2);
  dby::Heap::push_heap(vec, 8);
  dby::Heap::push_heap(vec, -1);
  dby::Heap::push_heap(vec, 0);
  dby::Heap::push_heap(vec, 9);
  dby::Heap::push_heap(vec, 4);

  while (vec.size()) {
    std::cout << "FRONT: " << vec.front() << '\n';
    // Remove top element of the heap
    dby::Heap::pop_heap(vec);
  }

  return 0;
}