Binary Heaps
Tags: computerscience, algorithms, datastructures, csharp
Published: 2019-11-25 00:38:09

## Resources

1. [Heap/Binary Heap Overview](https://www.interviewcake.com/concept/java/heap)
1. [Binary Heap/Priority Queue Overview](https://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html)
1. [Another Binary Heap Overview](https://brilliant.org/wiki/binary-heap/)
1. [Overview with implementation (missing heapsort)](https://www.geeksforgeeks.org/binary-heap/)
1. [Heapsort implementation](https://www.geeksforgeeks.org/heap-sort/)
1. [In depth detail of operations with diagrams + code for each](https://www.hackerearth.com/practice/notes/heaps-and-priority-queues/)
1. [Similar to previous, each page discusses a different aspect/operation + code](https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_binary_heap.htm)
1. [In depth implementation](https://runestone.academy/runestone/books/published/pythonds/Trees/BinaryHeapImplementation.html)

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**](https://en.wikipedia.org/wiki/Min-max_heap#Description)
* 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](https://dev.to/jjb/cs-level-up-series-part-0-cco), I link to [a medium article](https://medium.com/@alimirio/before-you-start-solving-problems-on-leetcode-prep-work-9d65fc964c6f) 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](https://introcs.cs.princeton.edu/java/24percolation/) (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](https://hyken.com/customer-service-culture/simple-doesnt-mean-easy/) cartoon:

![](https://hyken.com/wp-content/uploads/Simple-Not-Easy-Low-Res-250x300.jpg)

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:

{% gist https://gist.github.com/jbolton209/1aba19a23b1b7e8bb67917fa82588930 %}

As always, if you found any errors in this post please let me know!