Skip to main content

Heap

Priority Queue​

  • Similar to normal queue except that each element has a certain priority
  • The priority of the elements in the priority queue determine the order in which elements are removed from the PQ
  • How does a PQ knows which element to remove (i.e how does it keep track of value and priority of each element) => [[Software Engineer/DSA/Heap#Heap| Heap]] because when we give more priority to smallest or the largest node in the tree as we can extract these node very efficiently using heaps (Heap is the not the only to implement PQ it's just the most common and efficient way)

Heap​

  • A heap is a tree based DS that satisfies the heap property: If A is a parent node of B then A is ordered with respect to B for all nodes A, B in the hope => This means that the value of the parent node always larger than or equal to the value of child node for all node, or vice versa
  • 2 types of Heap
    - Max Heap: value of parent always larger than value of children
    - Min Heap: value of parent always smaller than value of children

Example: https://leetcode.com/problems/kth-largest-element-in-an-array/description/

  • Most basic use of heap
def findKthLargest(self, nums: List[int], k: int) -> int:
    heap = []
    
    for num in nums:
        heapq.heappush(heap, num)

        if len(heap) > k:
            heapq.heappop(heap)

    return heapq.heappop(heap)
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        frequency = {}
        for num in nums:
            if num not in frequency:
                frequency[num] = 0
            frequency[num] +=1
        
        items = [(-freq, num) for num, freq in frequency.items()]
        heapq.heapify(items)
        
        result = []
        for i in range(k):
            freq, num = heapq.heappop(items)
            result.append(num)
            
        return result

NOTES: heapq.heapify in python creates a min heap by default, if we want a max heap, we can multiply all value by -1 as seen in the code above (where we do -freq )

https://leetcode.com/problems/meeting-rooms-ii

def minMeetingRooms(self, intervals: List[List[int]]) -> int:
    # this can be thought of as occupying room
    heap = []
    intervals.sort()
    heapq.heappush(heap, intervals[0][1])

    for start, end in intervals[1:]:
        # free up a room by popping it off the heap
        if heap[0] <= start:
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    
    return len(heap)

https://leetcode.com/problems/car-pooling

 def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    trips.sort(key=lambda t: t[1])
    cur_pass = 0
    heap = []

    for num_pass, start, end in trips:
        while heap and heap[0][0] <= start:
            cur_pass -= heap[0][1]
            heapq.heappop(heap)
        
        cur_pass += num_pass
        if cur_pass > capacity:
            return False
        heapq.heappush(heap, (end, num_pass))

    return True