Heap

A heap is a complete binary tree that satisfies the heap property: a parent node is always less/greater than its children. Every subtree must also be a heap. There are two types of heaps:

• Min Heap: The root contains the smallest value.
• Max Heap: The root contains the largest value.

Common heap operations:

li = [1, 2, 3]

heapq.heapify(li) # Construct heap from list. Time: O(n)
heapq.heappush(li, 4) # Insert node. Time: O(log n)
heapq.heappop(li) # Remove root node. Time: O(log n)

• Python's heapq module creates a min heap.
• To implement a max heap, multiply the values by -1. (Newer versions of Python have a native max heap.)

Common uses:

• Implement priority queues (max/min value stays on top).
• Heap sort: involves removing the root node from a min heap n times. Time: O(n * log n)
• For graphing algorithms (e.g. Dijkstra's algorithm)

def findKthLargest(nums: List[int], k: int) -> int:
    # Create a min heap containing at most k nodes
    heap = []
    for i in range(k):
        heapq.heappush(heap, nums[i])

    # Add remainder of nums into heap, maintaining k size
    for i in range(k, len(nums)):
        if nums[i] > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, nums[i])

    # The heap will contain the k largest values in nums
    return heap[0]

Time: O(n * log k)

Space: O(k)

# nums1 = [1, 2, 4], nums2 = [1, 3, 5]
# Visualize the pair sums in a matrix
#               nums2
#            1    3    5
# nums1  1  [2]  [4]  [6]
#        2  [3]  [5]  [7]
#        4  [5]  [7]  [9]
#
# Each row in the matrix is a sorted list
# The goal is to merge every row into one sorted list, keeping the first k elements

def kSmallestPairs(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
    # Min heap holding tuples: (sum, index1, index2)
    heap, answer = [], []

    # Add the first element of every row (up to k) in the sum matrix
    # If k < len(nums1), remainder of nums1 can be ignored because
    #   the values will never be part of the answer
    # This only works because nums1 and nums2 are sorted
    for i in range(min(k, len(nums1))):
        heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))

    while len(answer) < k:
        _, i1, i2 = heapq.heappop(heap)

        answer.append([nums1[i1], nums2[i2]])

        # When element in a matrix row is processed, add next element in row
        if i2 + 1 < len(nums2):
            heapq.heappush(heap, (nums1[i1] + nums2[i2 + 1], i1, i2 + 1))

    return answer

Time: O(k * log k)

Space: O(k)