Min Heap Implementation

Min Heap Implementation video (42 minutes) (Spring 2021)

Priority Queue and Min Heap

In this lecture, we are implementing the Priority Queue ADT, using a Min Heap as the underlying data structure.

Min Heaps have the smallest element at the root of the heap. This gives the smallest element the highest priority in the Priority Queue.

The MinHeap class

We will implement a non-template heap, using vector as the array container.

class MinHeap {
  vector<char> heap;
  //... to be continued, see below

Helper Functions

Parent and Child node index helpers are static, since they don't depend on the state of any certain instance of the MinHeap class.

  static int parent_index(int index) {
    return (index - 1) / 2;
  }

  static int left_index(int index) {
    return 2 * index + 1;
  }

  static int right_index(int index) {
    return 2 * index + 2;
  }

Helpers for "if a child exists" for a certain node in the heap. A node will never have a right child without having a left child, due to the left-right filling in a full tree.

Comparing the possible index of a left/right child against the heap's array size is an easy way to tell if the index is valid, aka, if the child exists.

  bool has_children(int index) const {
    return has_left_child(index);
  }

  bool has_left_child(int index) const {
    return left_index(index) < heap.size();
  }

  bool has_right_child(int index) const {
    return right_index(index) < heap.size();
  }

There's no guarantee that a certain child is smaller or larger than the other. Just that they're both larger then the parent node, in a Min Heap.

  int smallest_child_index(int index) const noexcept {
    if (has_right_child(index)) {
      int l = left_index(index), r = l + 1;
      return heap[l] < heap[r] ? l : r;
    } else {  // if (has_left_child(index))
      return left_index(index);
    }
  }

Heap Operations

push()

Insert new element into the next available spot, aka back of the vector, aka bottom-right of the heap tree.

Then, percolate the new element up, swapping with parent, until the min-heap order property is valid again.

  void push(char c) {
    heap.push_back(c);
    // Note: We don't have to check if i != 0 because parent_index(0) == 0 and
    //   heap[0] is never less than heap[parent_index(0)]
    for (
        int i = heap.size() - 1, pi = parent_index(i);
        heap[i] < heap[pi];
        i = pi, pi = parent_index(i)) {
      swap(heap[i], heap[pi]);
    }
  }

pop()

Remove the root of the heap tree, aka the smallest element in a Min Heap, aka the element with highest priority in a Priority Queue.

Put the last element in the heap at the empty root position.

Then, percolate the new root down, swapping with the smaller child, until the min-heap order property is valid again.

  void pop() {
    swap(heap.front(), heap.back());
    heap.pop_back();

    for (
        int i = 0, sci = smallest_child_index(0);
        has_children(i) && heap[i] > heap[sci];
        i = sci, sci = smallest_child_index(i)) {
      swap(heap[i], heap[sci]);
    }
  }

top() and empty()

Easy implementation of top, using std::vector::front(), aka, 0th index of the "array"/vector

Also using std::vector::empty() to determine empty().

  char top() const {
    return heap.front();
  }

  bool empty() const {
    return heap.empty();
  }

Complete Example Code

This is also available, attached to the module.

#include <iostream>
#include <vector>
#include <utility>

using std::cout;
using std::endl;
using std::swap;
using std::vector;

class MinHeap {
  vector<char> heap;

  static int parent_index(int index) {
    return (index - 1) / 2;
  }

  static int left_index(int index) {
    return 2 * index + 1;
  }

  static int right_index(int index) {
    return 2 * index + 2;
  }

  bool has_children(int index) const {
    return has_left_child(index);
  }

  bool has_left_child(int index) const {
    return left_index(index) < heap.size();
  }

  bool has_right_child(int index) const {
    return right_index(index) < heap.size();
  }

  int smallest_child_index(int index) const noexcept {
    if (has_right_child(index)) {
      int l = left_index(index), r = l + 1;
      return heap[l] < heap[r] ? l : r;
    } else {  // if (has_left_child(index))
      return left_index(index);
    }
  }

public:
  void push(char c) {
    heap.push_back(c);
    // Note: We don't have to check if i != 0 because parent_index(0) == 0 and
    //   heap[0] is never less than heap[parent_index(0)]
    for (
        int i = heap.size() - 1, pi = parent_index(i);
        heap[i] < heap[pi];
        i = pi, pi = parent_index(i)) {
      swap(heap[i], heap[pi]);
    }
  }

  void pop() {
    swap(heap.front(), heap.back());
    heap.pop_back();

    for (
        int i = 0, sci = smallest_child_index(0);
        has_children(i) && heap[i] > heap[sci];
        i = sci, sci = smallest_child_index(i)) {
      swap(heap[i], heap[sci]);
    }
  }

  char top() const {
    return heap.front();
  }

  bool empty() const {
    return heap.empty();
  }
};

int main() {
    cout << "Priority Queues" << endl;
    MinHeap h;
  h.push('b');
  h.push('x');
  h.push('a');
  h.push('y');

  while(!h.empty()) {
    cout << h.top() << endl;
    h.pop();
  }

    return 0;
}

Thanks

Thanks to Brian Foster for writing up these notes based on the video lectures.