Heaps

Intro

Binary Heap is a Binary Tree with 2 more specifications (heap property)

• shape - a heap must be a complete tree

  • all the levels of the tree must be filled, except maybe the last one
  • last level must have the left-most nodes filled, always!

  

• order - root properties

Min Binary Heap

• every node is smaller than its children
• smallest value at the top

Max Binary Heap

• every node is bigger than its children
• greatest value at the top

Fibonacci Heaps

Binomial Heaps

Usage

• ‣ is often implemented using a Heap (items are enqueued by adding them to the heap, lowest/highest-priority item can quickly be grabbed from the top)
• when it’s necessary to repeatedly remove the object with the highest (or lowest) priority
• when insertions need to be interspersed with removals of the root node

Comparison

• Binary Heaps are typically constructed in-place in the same array where the elements are stored, with an implicit structure and no extra memory overhead, whereas **Radix Trees** use an explicit structure that requires additional memory beyond the stored keys

Advantages

• quickly access the smallest item
  • binary heaps allow you to grab the smallest item (the root) in O(1) time while keeping other operations relatively cheap (O(log(n)) time)
• space efficient
  • binary heaps are usually implemented with lists, saving the overhead cost of storing pointers to child nodes

Disadvantages

• limited fast search
  • binary heaps only provide easy access to the smallest item, finding other items in the heap takes O(n) time since we have to iterate through all the nodes

Problems

• [ ] Merge K Sorted Lists
• [ ] Top K Frequent Elements
• [ ] K Closest Points to Origin
• [ ] Find Median from Data Stream
• [ ] Sliding window Median
• [ ] Maximize Capital/IPO
• [ ] Minimum Cost to connect sticks/ropes
• [ ] Meeting Rooms II
• [ ] Employee free time
• [ ] Minimum cost to hire K workers
• [ ] Minimum number of CPU (Task scheduler)
• [ ] Minimum number of Refueling stops
• [ ] Building Heap from Array
• [ ] Heap Sort - Cpp Solution
• [ ] Maximum of all subarrays of size k - Cpp Solution
• [ ] k largest elements - Cpp Solution
• [ ] Kth smallest element - Cpp Solution
• [ ] Merge k Sorted Arrays - Cpp Solution
• [ ] Merge two binary Max heaps - Cpp Solution
• [ ] K-th Largest Sum Contiguous Subarray
• [ ] Reorganize String - Cpp Solution
• [ ] Merge K sorted linked lists - Cpp Solution
• [ ] Smallest range in K lists - Cpp Solution
• [ ] Find median in a stream - Cpp Solution
• [ ] Is Binary Tree Heap - Cpp Solution
• [ ] Minimum Cost of ropes - Cpp Solution
• [ ] Convert BST to Min Heap
• [ ] Convert min Heap to max Heap
• [ ] Rearrange characters - Cpp Solution
• [ ] Minimum sum - Cpp Solution

Corner CasesCorner Cases

• can contain duplicate values

• doesn’t follow the rules of a binary search tree, only ordering that matters is the heap-order property (i.e., ordering of parent nodes compared to their children)

• doesn’t follow the rules of a binary search tree, only ordering that matters is the heap-order property (i.e., ordering of parent nodes compared to their children)

  

Implementation

Binary Heap is implemented as Complete Binary Tree (it's also Balanced ⇒ height of the tree is log(n)) **where:

• each level is filled up before another level is added
• the bottom tier is filled in from left to right

⇒ this allows us to efficiently store our Heap as a List:

Algorithms

Heap Sort

• make a heap out of the list and then remove items one at a time in sorted order

Prim's Minimal-Spanning-Tree Algorithm

Dijkstra's Shortest-Path Algorithm

Selection Algorithms (kth smallest/biggest)

Patterns

‣

‣

‣

Code

In Python, it is available using heapq module.

heapify(iterable)

• used to convert the iterable into a heap data structure. i.e. in heap order

heappush(heap, ele)

• used to insert the element mentioned in its arguments into heap
• the order is adjusted, so that heap structure is maintained

heappop(heap)

• used to remove and return the smallest element from heap
• the order is adjusted, so that heap structure is maintained

heappushpop(heap, ele)

• combines the functioning of both push and pop operations in one statement, increasing efficiency
• the order is adjusted, so that heap structure is maintained

heapreplace(heap, ele)

• inserts and pops element in one statement, but it is different from the above function
• in this, the element is first popped, then the element is pushed i.e, the value larger than the pushed value can be returned
• returns the smallest value originally in the heap regardless of the pushed element as opposed to heappushpop()

nlargest(k, iterable, key = fun)