Minimum Ordered Heap

A Minimum Ordered Heap, also known as a MinHeap, is a data structure that is used when you are trying to access minimum values of arbitrarily sized list. It is a specific form of a Binary Heap, which is itself a more specific version of a Binary Tree.

As described on its Wikipedia entry, a tree must conform to the following two properties to be considered a Binary Heap.

• Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

• Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order.

Insertion of an item takes an average of O(lg N) time. Removal of items, similarly, takes O(lg N) time.

The process of converting an unsorted tree into a MinHeap is commonly called Heapify.

Plain Old Data

The plain old data for a MinHeap is just a vector of entries, each containing a key and value.

#include <vector>

using namespace std;

template <typename keyType, typename valType>
struct MinHeap {
  struct Entry {
    keyType key;
    valType val;
  };
  vector<Entry> arr;
  
  /**
   * Functions...
   */
};

Basic Helpers

int size() { return arr.size(); }

bool empty() { return size() == 0; }

void display() { 
  // Only works if types implements operator<<
  for (auto entry : arr)
    cout << entry.key<< "(val=" << entry.val << ")" << endl;
}

bool contains(MyNode v) {
  // Only works if valType implements operator==
  return find(arr.begin(), arr.end(), v) != arr.end();
}

Getting Parent and Children Entries

To obtain the matrix/vector index for a particular entry's parent or child, a simple function can be applied:

int parentIndex(int index) { return (index - 1) / 2; }
int leftChildIndex(int index) { return 2 * index + 1; }
int rightChildIndex(int index) { return 2 * index + 2; }

Heapify Down

void heapifyDown(int i) {
  int left = leftChildIndex(i);
  int right = rightChildIndex(i);
  int smallest = i;
  
  if (left < size() && arr[left].cost < arr[i].key)
    smallest = left;
    
  if (right < size() && arr[right].cost < arr[smallest].key)
    smallest = right;
    
  if (smallest != i) {
    swap(arr[i], arr[smallest]);
    heapifyDown(smallest);
  }
}

Heapify Up

void heapifyUp(int x) {
  if (x && (arr[parentIndex(x)].key> arr[x].key)) {
    swap(arr[x], arr[parentIndex(x)]);
    heapifyUp(parentIndex(x));
  }
}

Inserting Entries

void insert(Entry k) {
  arr.push_back(k);
  heapifyUp(size() - 1);
}

Removing the Minimum Entry

Entry removeMin() {
    auto temp = arr[0];
    arr[0] = arr.back();
    arr.pop_back();
    heapifyDown(0);
    return temp;
}