Writing your own heap in Python


  • 0
    E

    Did anyone try to write their own heap in Python?

    This is how I did it, and get time limit exceeded, but I think my implementation is fine.

    It finishes in 0.5s for the problem test case on my local machine.

    I am guessing that the C implementation of heapq is simply much faster than what can be achieved writing in Python itself.

    Did anyone write their own heap with Python and succeed?


  • 0

    What makes you think heapq is implemented in C?


  • 0
    E
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class MinHeap(object):
        def __init__(self):
            self.data = [0]
        
        def push(self, x):
            self.data.append(x)
            self.percolateUp(len(self.data)-1)
        
        def pop(self):
            res = self.data[1]
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            self.data.pop()
            self.percolateDown(1)
            return res
        
        def percolateUp(self, idx):
            while idx > 1:
                pa = idx / 2
                if self.data[pa][0] > self.data[idx][0]:
                    self.data[pa], self.data[idx] = self.data[idx], self.data[pa]
                idx = pa
                
        def percolateDown(self, idx):
            while 2 * idx < len(self.data):
                child = 2 * idx
                if 2 * idx + 1 < len(self.data) and self.data[2*idx+1][0] < self.data[2*idx][0]:
                    child = 2 * idx + 1
                if self.data[idx][0] > self.data[child][0]:
                    self.data[child], self.data[idx] = self.data[idx], self.data[child]
                idx = child
    
    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            """
            h = MinHeap()
            for l in lists:
                if l: h.push((l.val, l))
            superhead = ListNode(0)
            spt = superhead
            while len(h.data) > 1:
                node = h.pop()[1]
                if node.next: h.push((node.next.val, node.next))
                spt.next = node
                spt = spt.next
            
            return superhead.next
            
            # from Queue import PriorityQueue
            # q = PriorityQueue()
            # for l in lists:
            #     if l: q.put((l.val, l))
            # superhead = ListNode(0)
            # spt = superhead
            # while q.qsize() != 0:
            #     node = q.get()[1]
            #     if node.next: q.put((node.next.val, node.next))
            #     spt.next = node
            #     spt = spt.next
            
            # return superhead.next
    

Log in to reply
 

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