Implement A Binary Heap - An Efficient Implementation of The Priority Queue ADT (Abstract Data Type)

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Implement a binary heap (a complete binary tree which satisfies the heap ordering property). It can be either a min or a max heap.
Video On Heap Sort: • Investigating Heap Sor...
Priority Queue ADT (Abstract Data Type)
The ADT's Fundamental API
isEmpty()
insertWithPriority()
pullHighestPriorityElement()
peek() (which is basically findMax() or findMin()) is O(1) in time complexity and this is crucial.
A heap is one maximally efficient implementation of a priority queue.
We can have:
-) a min heap: min element can be peeked in constant time.
-) or a max heap: max element can be peeked in constant time.
The name of the heap indicates what we can peek in O(1) time.
It does not matter how we implement this as long as we support the expected behaviors of the ADT thus giving our caller what they want from our heap data structure.
A binary heap is a complete binary tree with a total ordering property hence making it a heap with O(1) peek time to the min or max element.
We can implement the heap with actual nodes or we can just use an array and use arithmetic to know who is a parent or left or right child of a specific index.
Insertion into a binary heap:
We insert the item to the "end" of the complete binary tree (bottom right of the tree).
We "bubble up" the item to restore the heap. We keep bubbling up while there is a parent to compare against and that parent is greater than (in the case of a min heap) or less than (in the case of a max heap) the item. In those cases, the item we are bubbling up dominates its parent.
Removal from a binary heap:
We give the caller the item at the top of the heap and place the item at the "end" of the heap at the very "top".
We then "bubble the item down" to restore the heap property.
Min Heap: We keep swapping the value with the smallest child if the smallest child is less than the value we are bubbling down.
Max Heap: We keep swapping the value with the largest child if the largest child is greater than the value we are bubbling down.
In this manner, we restore the heap ordering property.
The critical thing is that we can have O(1) knowledge of the min or max of a set of data, whenever you see a problem dealing with sizes think of a min or max heap.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech