# Python solution using heapq with the official way to delete

• 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
counter = itertools.count()     # unique sequence count

count = next(counter)
heappush(pq, entry)

entry[-1] = REMOVED

'Remove and return the lowest priority task. Raise KeyError if empty.'
while pq:
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

``````

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