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?
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.