What is Heap
Heap is a binary balanced tree that you fill the node from top to bottom and from left to right. There are 2 type of heaps: max-heap and min-heap. Max-Heap has parent >= children while Min-Heap has parent <= children. You can represent Heap in tree and array data structure. More detailed below.
Represent Heap in Tree and Array Structure
Below is a diagram of a Max-Heap in Tree and show you how to convert it to array as well.
If you want to better understand Heap, I highly recommend you to go thru the following videos from Paul. It shows you how to add/remove items from Heap and how to represent heap tree in array as well. For example, for any parent with index n, it will have children located at 2n+1 and 2n+2 indices. On the other hand, you can find its parent by using the formula of floor(n/2). Enough said, check out Paul’s videos below:
- Introduction to a Heap , Part 1 – The Structure of Heap , How to Add an Item
- Introduction to a Heap , Part 2 – How to Remove an Item from a Heap
- Introduction to a Heap , Part 3 – Describing a Heap as an Array
Usage of Heap
A heap could be used to implement a priority queue, which is a queue that orders entities not on FIFO basis but on a priority basis. So, since the heap has the minimum or the maximum key at the top, the next “priority” item is at the top with a removal time of 0(1). And each time the root node is removed, the heap will be restructured as what Paul described in his videos.
Also, Heaps are used in the Heap Sorting algorithm which has the worst case performance of O (n log n). Is it the best sorting algorithm? It depends! For critical applications that requires guarantees of speed performance, heapsort is the right way to go as it is consistently at O (n log n). However, heapsort also got few caveats itself like:
- Not as good locality of reference as it jumps around quite a bit.
- It is not an obvious candidate for a parallel algorithm like quicksort, mergesort and MSD radix sort.
- It cannot be used in external sort like mergesort. If you have data bigger than your memory, you should go for mergesort instead.
NOTE: Locality of reference is talking about the next thing to be accessed is usually close in memory to the thing you just looked at.