In this lesson, you’ll see the final optimal solution to solving the
merge_k_lists hard interview question. The solution takes advantage of the
PriorityQueue abstract data type, which is similar to a queue but associates each element with a priority. Getting an element, it retrieves the element with the highest priority. Both
.get() take logarithmic time.
Here’s an example:
>>> from queue import PriorityQueue >>> pq = PriorityQueue() >>> pq.put(2) >>> pq.put(1) >>> pq.put(3) >>> pq.get() 1 >>> pq.get() 2 >>> pq.get() 3 >>> pq.empty() True >>> pq.put((1, "hello")) >>> pq.put((2, "world")) >>> pq.get() (1, "hello") >>> pq.get() (2, "world")
You’ll see all solutions at the end of the course.