0.3 Heap
min-heap and max-heap
A min-heap is a binary tree such that the data contained in each node is less than (or equal to) the data in that node's children.
A max-heap is a binary tree such that the data contained in each node is greater than (or equal to) the data in that node's children.
heapq in Python
heapq.heappush(heap, item)
Push the value item onto the heap, maintaining the heap invariant.
heapq.heappop(heap)
Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].
heapq.heappushpop(heap, item)
Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().
heapq.heapify(x)
Transform list x into a heap, in-place, in linear time.
heapq with custom compare predicate
According to the heapq documentation, the way to customize the heap order is to have each element on the heap to be a tuple, with the first tuple element being one that accepts normal Python comparisons.
max-heap implementation in Python
The easiest way is to invert the value of the keys and use heapq. For example, turn 1000.0 into -1000.0 and 5.0 into -5.0.
Problems
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Time: O(nlogk)
We maintain a min-heap with size k, where k is the total items in the lists. For each item from the lists, we check once. Pushing the item into the heap costs O(k), and popping the min out of the min-heap costs O(1). So the total time is O(nlogk), n is the total items in all lists.
LC 378. Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.