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?
CodePudding user response:
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.