Min Heap implementation [C++]

Question

I've never had my C++ code reviewed before so I'd appreciate any feedback. Although my main focus was not on the implementation of the algorithm itself, any suggestions regarding improving it would be welcome. I'm mostly looking for C++ related feedback though.

#include <iostream>
#include <vector>

using namespace std;

class MinHeap {
public:
  void push(int num) {
    /* add num to end of the heap and rearrange by up-heap */
    heap.push_back(num);
    int ind = heap.size() - 1;

    if (heap.size() > 1) {
      int par = parent_index(ind);

      while (heap[ind] < heap[par]) {
        swap(heap[ind], heap[par]);
        ind = par;
        if (ind == 0) break;
        par = parent_index(ind);
      }
    }
  }

  void pop() {
    /* pop the element at the of the heap and finding a new top
    by replacing with the last element and performing a down-heap */
    if (heap.size() == 1) heap.pop_back();
    else if (heap.size() > 1) {
      swap(heap[0], heap.back());
      heap.pop_back();
      int ind = 0;
      int min_c = get_min_child(ind);

      while (heap[min_c] < heap[ind]) {
        swap(heap[min_c], heap[ind]);
        ind = min_c;
        if (child_count(ind) == 0) break;
        min_c = get_min_child(ind);
      }
    }
  }

  int top() {
    /* return element at the top of the heap (should be the min) */
    return heap.front();
  }

private:
  vector<int> heap;

  int get_min_child(int index) {
    /* find the smaller child of a node given by index */
    if (index < heap.size() - 2) {
      int left = left_child_index(index);
      int right = right_child_index(index);
      return (heap[left] < heap[right]) ? left : right;
    }
    else if (index < heap.size() - 1) {
      return left_child_index(index);
    }
    else throw invalid_argument("node has no children");
  }

  int parent_index(int index) {
    /* return index of parent node */
    if (index > 0) {
      return (index - 1) / 2;
    }
    else throw out_of_range("Trying to access root parent");
  }

  int child_count(int index) {
    /* return the number of children a given node has */
    if (2*index + 2 < heap.size()) return 2;
    else if (2*index + 1 < heap.size()) return 1;
    else return 0;
  }

  int left_child_index(int index) {
    int ind = 2*index + 1;
    if (ind < heap.size()) return ind;
    else throw out_of_range("Index out of range");
  }

  int right_child_index(int index) {
    int ind = 2*index + 2;
    if (ind < heap.size()) return ind;
    else throw out_of_range("Index out of range");
  }
};    

Answer 1

Here's my two cents:

1. Do not using namespace std;. It causes serious problems and is considered bad practice. See Why is using namespace std; considered bad practice?.

2. Consider wrapping your class in a header so that it can be reused. Use an include guard.

3. MinHeap is a common name that may cause name clash. Consider placing it in a namespace.

4. MinHeap only supports ints. You can make MinHeap a template.

5. Right now MinHeap can only be default initialized to empty. Consider adding a constructor to initialize the MinHeap with a list of values.

6. Your comments apply to the function, instead of the first line of the function body. They should really go outside the function.

   // this function foos the bar
   void foo(int bar)
   {
       ...
   }
   

7. You use int for indexes. This is not good because int may be too narrow — INT_MAX may be as small as 32767. Use std::size_t instead.

8. All of your functions that return an index have the suffix _index, except get_min_child. I would suggest renaming it to min_child_index to be consistent.

9. Don't write the whole branch on the same line. This decreases readability. Instead of

   if (2*index + 2 < heap.size()) return 2;
   else if (2*index + 1 < heap.size()) return 1;
   else return 0;
   

   Do

   if (2*index + 2 < heap.size())
       return 2;
   else if (2*index + 1 < heap.size())
       return 1;
   else
       return 0;
   

10. In left_child_index and right_child_index, ind can be computed in the if statement. (C++17)

11. You swap(heap[0], heap.back()) then immediately heap.pop_back(). You are not doing heap sort, you are popping the value. Just heap[0] = heap.back().

12. Incidentally, the standard library offers a couple of heap operations, and also priority_queue. Maybe you can use them to simplify your implementation.

Answer 2

L. F. gave a good review, but there is more:

1. Exceptions are not for programmer errors. That's what asserts are for.

2. Modularise your code:

   Extract down_heap() and up_heap() as free functions, making the algorithm available for anyone wanting to manipulate a heap.
   They should accept an iterator-range and a comparator, with the default being std::less<>().

3. Mark things noexcept if you can. Consider conditional noexcept too.

4. Also, make them constexpr if applicable.