4
\$\begingroup\$

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

}
\$\endgroup\$
2
\$\begingroup\$
  • 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.