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!

3 thoughts on “A Beginner’s Guide to Binary Heaps”

1. Kaan says:

Very clear explanation!

2. I see you don’t monetize devyashis.me, don’t waste
your traffic, you can earn additional cash every
month with new monetization method. This is the best adsense alternative for any type of website (they approve all sites),
for more info simply search in gooogle: murgrabia’s
tools

1. yash101 says:

I am not considering monetization currently.

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