Unorderable type error while pushing into heap

Question

I have a list of heads of N Linked Lists which I am trying to merge based on their value using heaps.

Since heapq works with first value in tuples for sorting in heap I wrote the following code:

 def mergeKLists(self, A): # A contains list of Linked list heads
    nodeList = []
    for i in A:
        nodeList.append((i.val,i)) # Creating a list of tuples : (value, Node address)
    heapq.heapify(nodeList)
    print(nodeList)

This works fine and creates a heap sorted on the 1st value in tuple. However when I am trying to push more elements on this heap it gives me a unordered type error:

    t = heapq.heappop(nodeList)
    node  = t[1]
    heapq.heappush(nodeList,(node.next.val,node.next)) # this throws error for node.next parameter

The error I get:

heapq.heappush(nodeList,(node.next.val,node))
TypeError: unorderable types: ListNode() < ListNode()

What am I doing incorrectly here?

Answer 1

This error will occur when the input lists have duplicate values. In that case the comparison of two tuples having the same first tuple member, will result in a comparison of the second tuple members, which is an operation that is not defined.

To avoid this error, either make the ListNode instances comparable, or add a member in your tuples, in the middle, which is unique:

nodeList.append((i.val, id(i), i))

...and adapt the rest of your code accordingly.