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

提问者：小点点

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

我正在解决Interviewbit代码挑战合并K排序列表：

合并k个排序链表并将其作为一个排序列表返回。

示例：

1 -> 10 -> 20
4 -> 11 -> 13
3 -> 8 -> 9

将导致

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返回最大的元素，就好像我们在处理一个最大堆，但我们不是！据我所知，这就是答案出错的地方。有人能提出heappop这样工作的原因吗？以及如何纠正它？

共1个答案

匿名用户

当我使用示例数据在本地运行您的代码时，我收到一个错误：

    heapify(minheap)

类型错误：<代码>

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

由于类ListNode已经由代码挑战框架定义，因此最好不要尝试使该类具有可比性。

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

与您的问题无关，但您应该只heapify一次，而不是在循环的每次迭代中。堆上的操作（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