For python, which heap implementation should you use?


  • 0
    I

    Python has heapq and PriorityQueue module. Which would you use, and why?


  • 0

    From the docs:

    The Queue module implements multi-producer, multi-consumer queues. It is especially useful in threaded programming when information must be exchanged safely between multiple threads.

    Since I'm not using multiple threads (at least not at LeetCode) and heapq seems to have functions more helpful to me, I'm just using heapq.

    In particular, PriorityQueue as far as I see doesn't have "peek" functionality. Probably because that would be bad in the context of multiple threads, as there'd be no guarantee that what you "peek" is what you next "get".


  • 0
    P

    Interesting. But how would you compare the ListNode's values since heapq.heappop(heap) assumes the item in heap is value? Should I only store the value of ListNode into heap and create a new ListNode when constructing my output?


  • 1

    @pjerryhu That's one way to do it, but I'd say it's more common to use (value, node) pairs. I did it both ways. Also see the second example in Basic Examples in the python docs.


  • 0
    P

    Cool, thanks. This is really helpful


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.