# Min heap C++ implementation

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);
}

}


• 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()) {

• 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.