Interviewbit - 合并 k 个排序链表：heappop returns max 元素而不是 min

Question

我正在解决 Interviewbit 代码挑战 Merge K Sorted Lists:

Merge k sorted linked lists and return it as one sorted list.

Example :
1 -> 10 -> 20
4 -> 11 -> 13
3 -> 8 -> 9
will result in
1 -> 3 -> 4 -> 8 -> 9 -> 10 -> 11 -> 13 -> 20

Python模板代码为：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param A : list of linked list
    # @return the head node in the linked list
    def mergeKLists(self, A):
        pass

这是我的 python 3 解决方案：

from heapq import heapify, heappop, heappush
class Solution:
    # @param A : list of linked list
    # @return the head node in the linked list
    def mergeKLists(self, A):
        minheap = [x for x in A]
        # print(minheap)
        # heapify(minheap)
        # print(minheap)
        head = tail = None 
        # print(minheap)
        while minheap: 
            # print(minheap)
            heapify(minheap)
            print([x.val for x in minheap])
            minimum = heappop(minheap)
            print(minimum.val)
            if head is None:
                head = minimum
                tail = minimum
            else:
                tail.next = minimum
                tail = minimum
            
            if minimum.next:
                heappush(minheap, minimum.next)

        return head

使用未注释的打印命令，您会注意到在 while 循环的中间运行中，heappop returns 最大的元素，就好像我们正在处理最大堆一样，我们不是！据我所知，这就是答案出错的地方。任何人都可以提出 heappop 为何如此工作的原因吗？以及如何纠正？

Answer 1

当我在本地运行您的代码和示例数据时，我收到错误消息：

    heapify(minheap)

TypeError: < not supported between instances of ListNode and ListNode

这是意料之中的。 ListNode 的模板定义不支持进行比较，heapify 函数需要比较给定列表中的项目。

由于 class ListNode 已经由 code-challenge 框架定义，最好不要尝试 make that class comparable.

我建议将元组放在堆上，这些元组具有列表节点实例作为成员，但它们的 val 属性值排在第一位，然后是列表的编号（在 A 中）他们起源于。作为第三个元组成员，您最终将拥有节点本身。这样比较就会起作用，因为元组在其成员时是可比较的。并且由于当第一个成员值相同时第二个元组成员将是 tie-breaker，因此第三个元组成员（列表节点实例）将永远不会受到比较。

与你的问题无关，但你应该只堆一次，而不是在循环的每次迭代中。堆上的操作（heappush、heappop）维护着堆属性，所以不需要第二次调用heapify。如果你在每次迭代中都这样做，你实际上会破坏你从使用堆中获得的效率优势。

这是您的代码更新后的更改：

from heapq import heapify, heappop, heappush

class Solution:
    def mergeKLists(self, A):
        # place comparable tuples in the heap 
        minheap = [(node.val, i, node) for i, node in enumerate(A)]
        heapify(minheap)  # call only once
        head = tail = None 
        while minheap: 
            # extract the tuple information we need
            _, i, minimum = heappop(minheap)
            if head is None:
                head = minimum
                tail = minimum
            else:
                tail.next = minimum
                tail = minimum
            
            minimum = minimum.next
            if minimum:
                # push a tuple, using same list index
                heappush(minheap, (minimum.val, i, minimum))

        return head

Interviewbit - 合并 k 个排序链表：heappop returns max 元素而不是 min

Interviewbit - Merge k sorted linked lists: heappop returns max element instead of min

heap

python-3.x

heapq