Heap – Theory

Heap is the underlying implementation of Priority Queue. A heap is implemented using a binary tree. A heap can be visualized to have a tree structure logically but internally it’s implemented an array.

For a binary heap we have O(log(n)) for insert, O(log(n)) for delete min and heap construction can be done in O(n). SO

Searching in a heap –  You need to search through every element in the heap in order to determine if an element is inside. One optimization is possible, though (we assume a max heap here). If you have reached a node with a lower value than the element you are searching for, you don’t need to search further from that node. However, even with this optimization, search is still O(N) (need to check N/2 nodes in average). SO

Heap is better at findMin/findMax (O(1)), while BST is good at all finds (O(logN)). Insert is O(logN) for both structures. If you only care about findMin/findMax (e.g. priority-related), go with heap. If you want everything sorted, go with BST.  SO

Why is Binary Heap Preferred over BST for Priority Queue? GFG

So why is Binary Heap Preferred for Priority Queue?

  • Since Binary Heap is implemented using arrays, there is always better locality of reference and operations are more cache friendly.
  • Although operations are of same time complexity, constants in Binary Search Tree are higher.
  • We can build a Binary Heap in O(n) time. Self Balancing BSTs require O(nLogn) time to construct.
  • Binary Heap doesn’t require extra space for pointers.
  • Binary Heap is easier to implement.
  • There are variations of Binary Heap like Fibonacci Heap that can support insert and decrease-key in Θ(1) time

Is Binary Heap always better?
Although Binary Heap is for Priority Queue, BSTs have their own advantages and the list of advantages is in-fact bigger compared to binary heap.

  • Searching an element in self-balancing BST is O(Logn) which is O(n) in Binary Heap.
  • We can print all elements of BST in sorted order in O(n) time, but Binary Heap requires O(nLogn) time.
  • Floor and ceil can be found in O(Logn) time.
  • K’th largest/smallest element be found in O(Logn) time by augmenting tree with an additional field.

Heapsort algorithm has limited uses because Quicksort is better in practice.

Priority Queues: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time. Binomoial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also in O(logn) time which is a O(n) operation in Binary Heap. Heap Implemented priority queues are used in Graph algorithms like Prim’s Algorithm and Dijkstra’s algorithm.

A typical Priority Queue requires following operations to be efficient.

Get Top Priority Element (Get minimum or maximum) – O(1)
Insert an element – O(Logn)
Remove top priority element – O(Logn)
Decrease Key -O(Logn)

Average binary heap insert is O(1)

Intuitive argument:

  • bottom tree levels have exponentially more elements than top levels, so new elements are almost certain to go at the bottom
  • heap insertion starts from the bottom, BST must start from the top

When is heap sort used –  Although QuickSort works better in practice, the advantage of HeapSort worst case upper bound of O(nLogn). MergeSort also has upper bound as O(nLogn) and works better in practice when compared to HeapSort. But MergeSort requires O(n) extra space HeapSort is not used much in practice, but can be useful in real time (or time bound where QuickSort doesn’t fit) embedded systems where less space is available (MergeSort doesn’t fit)





Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s