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.