We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Heap
  4. QHEAP1
  5. Discussions

QHEAP1

  • pdog1111
     + 5 comments

    simple solution in python using heapq. the trick is to use an item_lookup set for lazy deletes.

    from sys import stdin
from heapq import heappush, heappop

heap = []
item_lookup = set()

def push(v):
    heappush(heap, v)
    item_lookup.add(v)
    
def discard(v):
    item_lookup.discard(v)
    
def print_min():
    while heap[0] not in item_lookup:
        heappop(heap)
      
    print heap[0]
    
cmds = {
    1: push,
    2: discard,
    3: print_min
}

n = int(stdin.readline())
for _ in range(n):
    data = map(int,stdin.readline().split(" "))
    cmds[data[0]](*data[1:])