Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Heap Sort
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.