Heap Lazy Deletion and Edition | Beats 98%
IntuitionWhen we read the description, There are data structures like Heap, TreeMap, SortedSet come to our mind.We definitely can do this using TreeMap, and i s
# Intuition
When we read the description, There are data structures like Heap, TreeMap, SortedSet come to our mind.

We definitely can do this using TreeMap, and i saw some popular solution also use TreeMap. The reason is that TreeMap make it easy and fast to locate the taskId (**O(1) time**) in the `edit` and `delete` operations. Heap, on the other side,  will take **O(n) time** to locate the taskId, thus, each `edit` and `delete` operation will take O(n) time.

Actually, there is a way to resolve the O(n) time searching for Heap -  Lazy edition and deletion. The basic idea is that we don't need to locate the taskId whenever we do `edit` or `deletion` opertions. We can first "log" the opertions in a map, and when we need to execTop, we can then check the log map to see any deletion/update we need to catch up. In this way, the time complexity would be:

Add/Edit: $$O(logn)$$ 
Remove: $$O(1)$$
Amortized time complexity of Exec: $$O(logn)$$


# Code
```python3 []
class TaskManager:

    def __init__(self, tasks: List[List[int]]):
        self.map = {}
        self.h = []
        for userId, taskId, priorityId in tasks:
            self.map[taskId] = (userId, priorityId)
            self.h.append((-priorityId, -taskId, userId))
        heapq.heapify(self.h)

        
    def add(self, userId: int, taskId: int, priority: int) -> None:
        self.map[taskId] = (userId, priority)
        heapq.heappush(self.h, (-priority, -taskId, userId))
        

    def edit(self, taskId: int, newPriority: int) -> None:
        userId, priority = self.map[taskId]
        self.add(userId, taskId, newPriority)

    def rmv(self, taskId: int) -> None:
        del(self.map[taskId])
        

    def execTop(self) -> int:
        while self.h:
            priority, taskId, userId = heapq.heappop(self.h)
            if -taskId not in self.map:
                continue
            
            userId, newPriority = self.map[-taskId]
            if newPriority != -priority:
                heapq.heappush(self.h, (-newPriority, taskId, userId))
                continue
            
            del self.map[-taskId]
            
            return userId
        return -1
['Heap (Priority Queue)', 'Python3']