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
```