CS Level Up Series (30 Part Series)

## Resources

- 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
`O(1)`

(constant). - 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[0]. It is an`O(n)`

operation. - Binary heaps are typically implemented using arrays. Space is
`O(n)`

. -
**Heapsort**is a sorting algorithm that transforms an input array into a heap, and then turns the resulting heap into a sorted collection[1]. -
**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.

[0] *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 `PercolateDown`

and `PercolateUp`

functions makes sense.

[1] 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!

CS Level Up Series (30 Part Series)

## Discussion