# A Beginner’s Guide to Binary Heaps

## HeapSort

Heaps are actually very useful for sorting. Using buildHeap(), we can effectively build a heap in $$O(n)$$ time, and then we can extract each minimum in the array in $$O(h)$$ time. This means that we can extract every element in sorted order in $$O(n\log n)$$.

std::vector<Element> sortAscending(std::vector<Element>& v) {
MinHeap minh;
minh.buildHeap(v);
while(minh.arr.size() != 0) {
minh.arr.push_back(minh.extractMin());
}

return minh.arr;
}

std::vector<Element> sortDescending(std::vector<Element>& v) {
MaxHeap maxh;
maxh.buildHeap(v);
while(maxh.arr.size() != 0) {
maxh.arr.push_back(maxh.extractMin());
}

return maxh.arr;
}

## Questions?

If you have any questions or concerns, or if I have done something wrong, please leave a comment and let me know!

## One thought on “A Beginner’s Guide to Binary Heaps”

1. Kaan says:

Very clear explanation!

This site uses Akismet to reduce spam. Learn how your comment data is processed.