CS Level Up Series (30 Part Series)
- Heap/Binary Heap Overview
- Binary Heap/Priority Queue Overview
- Another Binary Heap Overview
- Overview with implementation (missing heapsort)
- Heapsort implementation
- In depth detail of operations with diagrams + code for each
- Similar to previous, each page discusses a different aspect/operation + code
- In depth implementation
Takeaways (for min-heap, but the same applies to max-heap):
- A binary heap is essentially a binary tree with either the smallest element at the top (min-heap), or the largest (max-heap).
- The two common types of binary heaps are: min-heap and max-heap. But there are also more exotic variants like the min-max-heap
- Retrieval of the smallest element in a min-heap is
- Inserting an element and extracting the min element are
O(log n)(logarithmic) operations.
- Extracting the min element from a min-heap is
O(log n). This is because a new root will need to be determined.
Heapify is a an operation that turns an array into a heap. It is an
- Binary heaps are typically implemented using arrays. Space is
- Heapsort is a sorting algorithm that transforms an input array into a heap, and then turns the resulting heap into a sorted collection.
- Priority Queues are often implemented using binary heaps. Which makes sense given in my first post of this series, I link to a medium article that groups together binary heap and priority queue into one bullet point.
 Heapify is a common term, and therefore important to know. However, in my implementation I opted to refer to the heapify operation as
PercolateDown instead. I had seen this terminology used elsewhere (both related, and not related, to heaps), and it reminded me of these exercises from Princeton (which I remember failing miserably years ago). It is also necessary to percolate elements up a heap when inserting or decreasing a key - so to me, having
PercolateUp functions makes sense.
 Heapsort does this in place, which means no additional memory is used to perform the sort. It does this by swapping elements around in the input array. (Technically extra space/memory is used for some temporary variables. But as long as the extra memory is
O(log n) or less, an algorithm can still be considered in-place)
Overall, binary heaps took a bit of time to fully grasp but once I properly understood them I found the implementation relatively simple.
Please remember that simple != easy, this is best illustrated by a Shep Hyken cartoon:
Anyway, here's the finished implementation of a min-heap with some test code. A max-heap would look very similar - so if you can implement one, you will be able to implement the other:
As always, if you found any errors in this post please let me know!