Write MergeKLists. Read k, then k sorted lists (size followed by the values). Merge them into one sorted sequence using a PriorityQueue that holds at most one entry per list: the current head of each list (value, list number, index in the list). Repeatedly remove the smallest entry, output it, and insert the next value of the same list. Equal values come out in list order.
Print the merged sequence, the list each value came from (A, B, C …), and the largest size the heap ever had.
For the input
3
3 1 4 9
2 2 3
4 0 5 6 10
the program prints
Merged: 0 1 2 3 4 5 6 9 10
Taken from lists: CABBACCAC
9 values, heap never larger than 3 (k = 3)