Python solution using heapq with the official way to delete

  • 1

    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:
        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.
   = 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.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:
            return self.heap[0]
        def delete(self, point):
            pid =
            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
            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:
                    # delete from heap
                    # 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
                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.