Min heap C++ implementation

Question

I have implemented a min heap in C++, and I want to improve it in every possible way. Could you please review it and let me know your suggestions/comments?

#include <iostream>
#include <vector>
#include <algorithm> // std::swap
class MinHeap {
 private: 
 std::vector<int> heap;
 void heapify(int);
 int parent(int);
 int left(int);
 int right(int);
 public: 
 void insert(int);
 int extractMin();
};
// heapifies down the index-i
void MinHeap::heapify(int i) {
 int l = left(i);
 int r = right(i);
 // find the smallest amongst the parent, it's left & right child
 int smallest;
 smallest = (l != -1 && heap[l] < heap[i]) ? l : i;
 smallest = (r != -1 && heap[r] < heap[smallest]) ? r : smallest;
 // If heap[i] (parent) is the smallest, then it is already a Heap!
 if (smallest != i) {
 std::swap(heap[i], heap[smallest]);
 heapify(smallest);
 }
}
// Returns the index of the left-child of the ith element
// Returns -1 if the index > heap size
int MinHeap::left(int i) {
 int l = (((2 * i) + 1) < heap.size() - 1) ? (2 * i) + 1 : -1;
 return l;
}
// Returns the index of the Right-child of the ith element
// Returns -1 if the index > heap size
int MinHeap::right(int i) {
 int r = (((2 * i) + 2) < heap.size() - 1)? (2 * i) + 2 : -1;
 return r;
}
// Returns the index of the Parent of the ith element
// Returns -1 if parent-index < 0 
int MinHeap::parent(int i) {
 int p = (((i - 1) / 2) >= 0)? (i - 1) / 2 : -1;
 return p;
}
// Returns the minimum element from the heap and also deletes it from the heap
int MinHeap::extractMin() {
 // back-up the root, it's the min value
 int min = heap[0];
 // copy the value of the very-last element into the root and delete the last element
 heap[0] = heap.back();
 heap.pop_back();
 // heapify-down the root
 heapify(0);
 return min;
}
// inserts a value at the right-spot in the heap, ensures the heap property is maintained.
void MinHeap::insert(int value) {
 // insert the new element at the end of heap
 heap.push_back(value);
 // bubble-up the new value to its right position, thus maintaining the heap property
 int i = heap.size() - 1;
 while (heap[parent(i)] > heap[i]) {
 std::swap(heap[parent(i)], heap[i]);
 i = parent(i);
 }
}

Answer 1

• Overall, LGTM.

• A protection against negative indices being passed to parent doesn't worth the effort. parent is a private method, so you are in control of the indices at all times. A strong indication that the protection is not needed is the fact that insert doesn't bother to test the return value for validity.

• Along the same line, left() and right() returning -1 doesn't look like a good idea. Effectively, you test the same condition twice: ((2 * i) + 1) < heap.size() - 1 in left, and l != -1 in heapify.

• Notice that anytime right is valid, left is also valid. That allows a certain optimization (see below).

• C++ is very good in recognizing tail recursion and optimizing it out. I strongly recommend to do it explicitly anyway.

• Combining the three bullets above, consider

  void heapify(int i)
  {
   while ((r = right(i)) < heap.size()) {
   follow your swapping logic
   }
   if ((l = left(i)) < heap_size()) { // No need to loop - it may only happen once!
   if (heap[l] < heap[i]) {
   std::swap(heap[i], heap[l]);
   }
   }
  }
  

• MinHeap::heapify is a misnomer, and somewhat confusing. Usually heapify refers to the process of turning an array into a heap. Your method is normally called sift_down.

• Too many comments to my taste.