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

Question

I'm solving the Interviewbit code challenge 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

The Python template code is:

# 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

Here's my python 3 solution for the same:

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

With the print commands that are uncommented, you'll notice that in the intermediate runs of the while loop, heappop returns the largest element, as if we were dealing with a max heap, which we're not! That's the place where the answer is going wrong as far as I can see. Can anyone suggest the reason for why heappop is working like this? And how that can be corrected?

„ you'll notice“ I’m afraid we don’t, since we cannot actually run the code with what is in the question. Please take another look at the How to Ask and especially the minimal reproducible example help pages and edit the question accordingly. — MisterMiyagi
– MisterMiyagi, Commented Jan 22, 2022 at 7:46
Note that heapq already ships with a helper to merge multiple iterable, provide each is internally sorted. — MisterMiyagi
– MisterMiyagi, Commented Jan 22, 2022 at 7:47
Hi. Provided the link to the exact question so that it can be reproduced exactly in the settings in which it is being attempted. Hope that helps and apologies for the earlier oversight. — K2G
– K2G, Commented Jan 22, 2022 at 7:50
No. Again, please take a look at the minimal reproducible example help page. Do not rely on external services being available to the people you are asking for help. Cut down the code to only the critical parts, provide a small sample input by hardcoding it into a piece of code that calls your algorithm properly. — MisterMiyagi
– MisterMiyagi, Commented Jan 22, 2022 at 7:53

trincot · Accepted Answer · 2022-01-22 15:52:06Z

When I run your code locally with sample data, I get an error on:

    heapify(minheap)

TypeError: < not supported between instances of ListNode and ListNode

This is expected. The template definition of ListNode shows no support for making comparisons, and a heapify function will need to compare the items in the given list.

As the class ListNode is already defined by the code-challenge framework, it is probably better not to try to make that class comparable.

I would propose to put tuples on the heap which have list node instances as members, but have their val attribute value come first, followed by the number of the list (in A) they originate from. As third tuple member you'd finally have the node itself. This way comparisons will work, since tuples are comparable when their members are. And since the second tuple member will be a tie-breaker when the first member value is the same, the third tuple member (the list node instance) will never be subject to a comparison.

Unrelated to your question, but you should only heapify once, not in each iteration of the loop. The actions on the heap (heappush, heappop) maintain the heap property, so there is no need for calling heapify a second time. If you do it in each iteration, you actually destroy the efficiency benefit you would get from using a heap.

Here is your code updated with that change:

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

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related