Interviewbit - Merge k sorted linked lists: heappop returns max element instead of min

I'm solving the Interviewbit code challenge Merge K Sorted Lists:

Merge k sorted linked lists and return it as one sorted list.

Example :

1 -> 10 -> 20
4 -> 11 -> 13
3 -> 8 -> 9

will result in

1 -> 3 -> 4 -> 8 -> 9 -> 10 -> 11 -> 13 -> 20

The Python template code is:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param A : list of linked list
    # @return the head node in the linked list
    def mergeKLists(self, A):
        pass

Here's my python 3 solution for the same:

from heapq import heapify, heappop, heappush
class Solution:
    # @param A : list of linked list
    # @return the head node in the linked list
    def mergeKLists(self, A):
        minheap = [x for x in A]
        # print(minheap)
        # heapify(minheap)
        # print(minheap)
        head = tail = None 
        # print(minheap)
        while minheap: 
            # print(minheap)
            heapify(minheap)
            print([x.val for x in minheap])
            minimum = heappop(minheap)
            print(minimum.val)
            if head is None:
                head = minimum
                tail = minimum
            else:
                tail.next = minimum
                tail = minimum
            
            if minimum.next:
                heappush(minheap, minimum.next)

        return head 

With the print commands that are uncommented, you'll notice that in the intermediate runs of the while loop, heappop returns the largest element, as if we were dealing with a max heap, which we're not! That's the place where the answer is going wrong as far as I can see. Can anyone suggest the reason for why heappop is working like this? And how that can be corrected?

When I run your code locally with sample data, I get an error on:

    heapify(minheap)

TypeError: < not supported between instances of ListNode and ListNode

This is expected. The template definition of ListNode shows no support for making comparisons, and a heapify function will need to compare the items in the given list.

As the class ListNode is already defined by the code-challenge framework, it is probably better not to try to make that class comparable.

I would propose to put tuples on the heap which have list node instances as members, but have their val attribute value come first, followed by the number of the list (in A) they originate from. As third tuple member you'd finally have the node itself. This way comparisons will work, since tuples are comparable when their members are. And since the second tuple member will be a tie-breaker when the first member value is the same, the third tuple member (the list node instance) will never be subject to a comparison.

Unrelated to your question, but you should only heapify once, not in each iteration of the loop. The actions on the heap (heappush, heappop) maintain the heap property, so there is no need for calling heapify a second time. If you do it in each iteration, you actually destroy the efficiency benefit you would get from using a heap.

Here is your code updated with that change:

from heapq import heapify, heappop, heappush

class Solution:
    def mergeKLists(self, A):
        # place comparable tuples in the heap 
        minheap = [(node.val, i, node) for i, node in enumerate(A)]
        heapify(minheap)  # call only once
        head = tail = None 
        while minheap: 
            # extract the tuple information we need
            _, i, minimum = heappop(minheap)
            if head is None:
                head = minimum
                tail = minimum
            else:
                tail.next = minimum
                tail = minimum
            
            minimum = minimum.next
            if minimum:
                # push a tuple, using same list index
                heappush(minheap, (minimum.val, i, minimum))

        return head