A Beginner’s Guide to Binary Heaps

Heap Operations

Element Class Definition and Helper Functions

class Element {
public:
  int key;
  int value;

  inline Element() :
    key(0),
    value(0)
  {}
};

size_t parent(size_t pos) {
  return (i - 1) / 2;
}

size_t left(size_t pos) {
  return 2 * i + 1;
}

size_t right(size_t pos) {
  return 2 * i + 2;
}

void swap(Element& a, Element& b) {
  Element& tmp = a;
  a = b;
  b = tmp;
}

MinHeap Class Definition

class MinHeap {
  std::vector<Element> arr;
  
  Element getMin();
  Element extractMin();
  void decreaseKey(size_t index, int new_key);
  void insert(Element e);
  void remove(size_t index);
  void buildHeap(std::vector<Element> elements);
  
};

MaxHeap Class Definition

class MaxHeap {
  std::vector<Element> arr;

  Element getMax();
  Element extractMax();
  void increaseKey(size_t index, int new_key);
  void insert(Element e);
  void remove(size_t index);
  void buildHeap(std::vector<Element> elements);
};

Heap getMin() / getMax() Operation

The function, getMin() returns the minimum element in a min-heap. This is relatively simple to do, because, the minimum element in a min-heap is the root node. In the second section, we discussed how the root node is the first element in the array containing the heap. Thus, the getMin() function would be implemented as such:

Element MinHeap::getMin() {
  if(arr.size() == 0)
    return Element();
  return arr[0];
}

Element MaxHeap::getMax() {
  if(arr.size() == 0)
    return Element();
  return arr[0];
}

The time complexity of getMin()/getMax() is \(O(1)\).

The space complexity of getMin()/getMax() is \(O(1)\) because no allocations are made throughout the algorithm.

Heap extractMin()/extractMax() Operation

The function, extractMin()/extractMax() returns the current minimum (or maximum) from the heap, and then removes it from the heap. The functions extractMin() and extractMax() can be implemented as such:

Element MinHeap::extractMin() {
  if(arr.size() == 0)
    return Element();

  Element root = arr[0];
  arr[0] = arr[arr.size() - 1];

  arr.pop_back();

  minHeapify(0);

  return root;
}

Element MaxHeap::extractMax() {
  if(arr.size() == 0)
    return Element();

  Element root = arr[0];
  arr[0] = arr[arr.size() - 1];

  arr.pop_back();

  maxHeapify(0);

  return root;
}

How does extractMin() / extractMax() work?

1. Check to see if the array is not empty. This would result in an error if true.
2. Store the root (0th element) in a temporary variable, \(root\).
3. Overwrite the root with the last element in the heap, \(arr[arr.\text{size}() – 1]\).
4. Reduce the size of the heap by one, by truncating the last value (arr.pop_back()).
5. Heapify the root (0th element).
6. Return original the root from the temporary variable.

The time complexity of these operations is \(O(h)=O(\lceil \log n\rceil)\), where \(h\) is the height of the tree

Heap minHeapify()/maxHeapify Operation

minHeapify() and maxHeapify are operations which heapify an element into its right place. a subtree with the root index passed in. The heapify operation assumes that the subtrees of the subtree being heapified are already heapified (proper heaps).

Both operations take a maximum time of \(O(h)\) where \(h\) is the height of the tree. Thus, the maximum time complexity of heapify() is \(O(\log n)\)

void MinHeap::minHeapify(size_t pos) {
  // Calculate the address of the left and right children
  int l = left(pos);
  int r = right(pos);
  // Initialize smallest so it is pointing to the parent node
  int smallest = pos;

  // These if statements set smallest to l or r if l or r are smaller
  // than the current smallest
  if(l < arr.size() && arr[l] < arr[pos].key) {
    smallest = l;
  }
  if(r < arr.size() && arr[r] < arr[smallest].key) {
    smallest = r;
  }

  // This if statement checks to see if smallest changed through
  // the two if statements. If it did, the smallest element is swapped
  // with the parent. Heapify is thereafter called on the new location
  // for the original root
  if(smallest != pos) {
    swap(arr[pos], arr[smallest]);
    minHeapify(smallest);
  }
}

void MaxHeap::maxHeapify(size_t pos) {
  // Calculate the address of the left and right children
  int l = left(pos);
  int r = right(pos);
  // Initialize the largest value to the root node
  int largest = pos;

  // These two if statements set largest to l or r respectively if
  // l or r is smaller than smallest.
  if(l < arr.size() && arr[l] > arr[pos].key) {
    largest = l;
  }
  if(r < arr.size() && arr[r] > arr[pos].key) {

    largest = r;
  }

  // This if statement checks to see if largest changed through
  // the two if statements. If it did, the largest element is swapped
  // with the parent. Heapify is thereafter called on the new location
  // for the original root
  if(largest != pos) {
    swap(arr[pos], arr[largest];
    maxHeapify(largest);
  }
}

How minHeapify() and maxHeapify() work:

1. Addresses of the left and right children are calculated by the first two lines
2. The smallest of, left, right and the current node is found using the first two if statements.
3. The third if statement checks to see if smallest or largest no longer point to the node pointed by pos.
   1. If smallest / largest does not equal pos, we swap the values of both, and then heapify the child pointed by smallest / largest.

Heap decreaseKey() and increaseKey() Operation

To decrease the key of a value in a min-heap, you may use the decreaseKey() operation.

To increase the key of a value in a max-heap, you may use the increaseKey() operation.

Both operations take \(O(\log n)\) time.

void MinHeap::decreaseKey(size_t position, int new_key) {
  arr[position].key = new_key;

  while(position != 0 && arr[parent(position)] > arr[position]) {
    swap(arr[position], arr[parent(position)]);
    position = parent(position);
  }
}

void MaxHeap::increaseKey(size_t position, int new_key) {
  arr[position].key = new_key;

  while(position != 0 && arr[parent(position)] < arr[position]) {
    swap(arr[position], arr[parent(position)]);
    position = parent(position);
  }
}

Heap insert() Operation

The insert() operation of a heap inserts a value in its correct position. It takes up to \(O(h)=O(\log n)\) time.

void MinHeap::insert(Element e) {
  size_t pos = arr.size();
  arr.push_back(e);

  while(pos != 0 && arr[parent(pos)] > arr[pos]) {
    swap(arr[pos], arr[parent(pos)]);
    pos = parent(pos);
  }
}

void MaxHeap::insert(Element e) {
  size_t pos = arr.size();
  arr.push_back(e);

  while(pos != 0 && arr[parent(pos)] < arr[pos]) {
    swap(arr[pos], arr[parent(pos)]);
    pos = parent(pos);
  }
}

To insert an element into a heap, the insert() operation inserts a key at the end of the array, and then moves it upwards in the tree until it is in the right spot.

Heap remove() Operation

To delete an element in a min-heap, we need to make it the root element, and then extract it. In a min-heap, we can do this by setting its key to the current root – 1, and in a max-heap, we can do this by setting the its key to the current root + 1. To move the element to its new position, we call decreaseKey() or increaseKey() respectively. This operation takes up to \(O(h)=O(\log n)\) time.

void MinHeap::remove(size_t index) {
  decreaseKey(i, arr[0].key - 1);
  extractMin();
}

void MaxHeap::remove(size_t index) {
  increaseKey(i, arr[0].key + 1);
  extractMin();
}

Heap buildHeap() Operation

Here is a function which builds a heap from an array:

BuildHeap() has a time complexity of \(O(n)\)

void MaxHeap::buildMaxHeap(std::vector<Element> array) {
  arr = array;
  for(size_t i = arr.size() / 2; i != 0; i--) {
    maxHeapify(i);
  }
}

void MinHeap::buildMaxHeap(std::vector<Element> array) {
  arr = array;
  for(size_t i = arr.size() / 2; i != 0; i--) {
    minHeapify(i);
  }
}