I'm working on Merge K Sorted Linked Lists from Leetcode and the optimal solution requires use of a heap. When unpacking the tuple from heapq.heappop()
, I figured I would use _, _, node
to unpack, as I'm not using the value or index anywhere else in the code. However this throws the following TypeError
:
I understand that this error is the result of the heap trying to compare the ListNode
object instead of the values and index, but this should not be the case as I've clearly defined it to compare the first 2 objects before the last. When unpacking with val, i, node = heapq.heappop(heap)
the code runs fine.
import heapq
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
dummy = ListNode()
curr = dummy
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node)) #Add to the heap. Compare by value, then index
while heap:
val, i, node = heapq.heappop(heap) #Working line
#_, _, node = heapq.heappop(heap) #Non-working line
curr.next = node
curr = node
node = node.next
if node: #If we're not at the end of the list, add to the heap
heapq.heappush(heap, (node.val, i, node))
return dummy.next
heapq.heappush(heap, (node.val, i, node))
. If you use_, _, node = heapq.heappop(heap)
then thei
value from your for-loop is used (sincei
does not get a new value in the while loop). If you useval, i, node = heapq.heappop(heap)
, theni
gets a new value. I am not sure if this is the actual cause of the error though.