Python solution using heapq with the official way to delete


  • 1
    B

    The python 2.7 documentation says we can delete an entry from heapq using a delete map:

    """
    Removing the entry or changing its priority is more difficult because it would break the heap structure invariants. So, a possible solution is to mark the existing entry as removed and add a new entry with the revised priority:
    """
    pq = []                         # list of entries arranged in a heap
    entry_finder = {}               # mapping of tasks to entries
    REMOVED = '<removed-task>'      # placeholder for a removed task
    counter = itertools.count()     # unique sequence count
    
    def add_task(task, priority=0):
        'Add a new task or update the priority of an existing task'
        if task in entry_finder:
            remove_task(task)
        count = next(counter)
        entry = [priority, count, task]
        entry_finder[task] = entry
        heappush(pq, entry)
    
    def remove_task(task):
        'Mark an existing task as REMOVED.  Raise KeyError if not found.'
        entry = entry_finder.pop(task)
        entry[-1] = REMOVED
    
    def pop_task():
        'Remove and return the lowest priority task. Raise KeyError if empty.'
        while pq:
            priority, count, task = heappop(pq)
            if task is not REMOVED:
                del entry_finder[task]
                return task
        raise KeyError('pop from an empty priority queue')
    

    The time complexity of pop_task() is still log(n), but the real time cost is way higher.
    Here is my implementation with my own heapq class with this delete method:

    class CriticalPoint(object):
        def __init__(self, id, a=True, x=0, h=0, p=-1):
            """
            Need an id to pair start and end so that we know which one to delete.
            """
            self.id = id     # unique identifier
            self.a  = a      # active
            self.x  = x      # point
            self.h  = h      # height
            
        def __cmp__(self, other):
            # python heapq pops the smallest one
            # reverse this to pop the largest one
            return other.h - self.h
            
        def __str__(self):
            return "%s#%s" % (self.id, self.h)
    
    
    class HeapQueueWithDelete(object):
        def __init__(self):
            self.heap = [CriticalPoint(id=-1)]
            self.delete_map = {}
        
        def push(self, point):
            heapq.heappush(self.heap, point)
            self.delete_map[str(point)] = point
                
        def peak(self):
            while self.heap and not self.heap[0].a:
                heapq.heappop(self.heap)
                
            return self.heap[0]
            
        def delete(self, point):
            pid = point.id
            prev_map_key = "%s#%s" % (pid, -point.h)
            prev_point = self.delete_map.pop(prev_map_key)
            prev_point.a = False
    
    
    class Solution(object):
        def getSkyline(self, buildings):
            """
            :type buildings: List[List[int]]
            :rtype: List[List[int]]
            """
            if not buildings:
                return []
                
            critical_points = []
            counter = itertools.count()
            for b in buildings:
                id = next(counter)
                critical_points.append(CriticalPoint(id, True, b[0], b[2]))
                critical_points.append(CriticalPoint(id, True, b[1], -b[2]))
            
            def custom_cmp(a, b):
                return a.x - b.x
    
            critical_points.sort(cmp=custom_cmp)
    
            result = []
            heap = HeapQueueWithDelete()
            prev = 0
            i = 0
            while i < len(critical_points):
                while i < len(critical_points):
                    cur_cp = critical_points[i]
                    # push into heap
                    if cur_cp.h > 0:
                        heap.push(cur_cp)
                    # delete from heap
                    else:
                        heap.delete(cur_cp)
                    
                    # continue to push/pop the ones at same x
                    if i + 1 < len(critical_points) and cur_cp.x == critical_points[i + 1].x:
                        i += 1
                    else:
                        break
                
                cur_max = heap.peak()
                if cur_max.h != prev:
                    result.append([cur_cp.x, cur_max.h])
                    prev = cur_max.h
                    
                i += 1
                
            return result
            
    

Log in to reply
 

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