Heap Sort

heapsort.cpp

#include <iostream>
#include <vector>

template <class T>
class MinHeap 
{
private:
    std::vector<T> m_vals;

public:
    MinHeap() {};

    void Insert(T val) {
        //add value to end of heap and 
        //then bubble repeatedly if it is smaller than parent

        m_vals.push_back(val);
        if (m_vals.size() <= 1)
            return;
        int idx = m_vals.size()-1;
        while (val<m_vals[GetParent(idx)]) {
            int idx_parent = GetParent(idx);
            std::swap(m_vals[idx], m_vals[idx_parent]);
            idx = idx_parent;
            if (GetParent(idx) == -1)
                return;
        }
    };

    bool DeleteMin() {
        //set root value to last heap child, which wipes root value.
        //then switch root with smallest child if it is smaller than root.
        //do that switching repeatedly until children are not smaller.
        //finally delete the the last element of m_vals vector.

        if (m_vals.size()==0)
            return false;
        if (m_vals.size()==1) {
            m_vals.pop_back();
            return true;
        }
        m_vals[0] = m_vals[m_vals.size()-1];
        m_vals.pop_back();
        int idx = 0;
        bool bContinue = true;
        while(bContinue) {
            int idx_l = GetLeftChild(idx);
            int idx_r = GetRightChild(idx);
            if (idx_l == -1 && idx_r == -1) {
                bContinue = false;
                break;
            }
            int idx_smallest_child = -1;
            if (idx_l == -1)
                idx_smallest_child = idx_r;
            else if (idx_r == -1)
                idx_smallest_child = idx_l;
            else
                idx_smallest_child = m_vals[idx_l] < m_vals[idx_r] ? idx_l : idx_r;
            if (m_vals[idx_smallest_child] >= m_vals[idx]) {
                bContinue = false;
                break;
            }
            std::swap(m_vals[idx], m_vals[idx_smallest_child]);
            idx = idx_smallest_child;
        }

        return true;
    };

    T GetMin() { 
        if (m_vals.size() == 0)
            return -1;
        return m_vals[0];
    }

    int GetSize() {
        return m_vals.size();
    }

private:
    int GetParent(int idx) {
        if (idx<=0)
            return -1;
        return (idx-1)/2; 
    }
    int GetLeftChild(int idx) {
        int child_idx = (idx*2)+1;
        return (child_idx >= m_vals.size() ? -1 : child_idx);
    }
    int GetRightChild(int idx) {
        int child_idx = (idx*2)+2;
        return (child_idx >= m_vals.size() ? -1 : child_idx);
    }


};

template <class T>
void heap_sort(std::vector<T>& nums) {
    MinHeap<T> heap;
    for (int i=0; i<nums.size(); i++)
        heap.Insert(nums[i]);

    for (int i=0; i<nums.size(); i++) {
        nums[i] = heap.GetMin();
        heap.DeleteMin();
    }
}

template <class T>
void print_v(const std::vector<T>& vals) {
    for (auto val : vals)
        std::cout << val << " ";
    std::cout << std::endl;
}

int main()
{
    std::vector<int> nums { 23,4,42,15,16,8 };
    print_v(nums);
    heap_sort(nums);
    print_v(nums);

    return 0;
}