Merge k Sorted Lists

# 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]:
        hp = []
        for idx, head in enumerate(lists):
            if head:
                heappush(hp, (head.val, idx))
                lists[idx] = head.next
        tmp = dummy = ListNode()
        while hp:
            val, idx = heappop(hp)
            tmp.next = ListNode(val)
            tmp = tmp.next
            if lists[idx] != None:
                heappush(hp, (lists[idx].val, idx))
                lists[idx] = lists[idx].next
        return dummy.next