daily pastebin goal
4%
SHARE
TWEET

Untitled

a guest Feb 23rd, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def siftup(ind):
  2.     global heap
  3.     while ind > 1 and heap[ind] > heap[ind // 2]:
  4.         heap[ind], heap[ind // 2] = heap[ind // 2], heap[ind]
  5.         ind //= 2
  6.     return ind
  7.  
  8.  
  9. def siftdown(ind):
  10.     global heap
  11.     while 2 * ind < len(heap):
  12.         best = 2 * ind
  13.         if  2 * ind + 1 < len(heap) and heap[best + 1] > heap[best]:
  14.             best += 1
  15.         if heap[ind] >= heap[best]:
  16.             return
  17.         heap[ind], heap[best] = heap[best], heap[ind]
  18.         ind = best
  19.  
  20.  
  21. def add(el):
  22.     global heap
  23.     heap.append(el)
  24.     siftup(len(heap) - 1)
  25.    
  26.  
  27. def remove(ind):
  28.     global heap
  29.     heap[ind], heap[-1] = heap[-1], heap[ind]
  30.     elem = heap.pop()
  31.     if ind == len(heap):
  32.         return elem
  33.     ind = siftup(ind)
  34.     siftdown(ind)
  35.     return elem
  36.  
  37. fin = open('priority-queue.in')
  38. commands = [s.rstrip().split() for s in fin.readlines()]
  39. fin.close()
  40. heap = [0]
  41. dic = {}
  42. fout = open('priority-queue.out', 'w')
  43. for s in commands:
  44.     if s[0] != 'POP':
  45.         s[2] = int(s[2])#priority
  46. for s in commands:
  47.     if s[0] == 'ADD':
  48.         add(s[2])
  49.         dic[s[1]] = s[2]
  50.     if s[0] == 'POP':
  51.         ans = remove(1)
  52.         for i in dic.keys():
  53.             if dic[i] == ans:
  54.                 print(i, dic[i], file = fout)
  55.                 dic[i] = 'nothing'
  56.                 break
  57.     if s[0] == 'CHANGE':
  58.         elem = dic[s[1]]
  59.         dic[s[1]] = s[2]
  60.         i = 1
  61.         while heap[i] != elem:
  62.             i += 1
  63.         heap[i] = s[2]
  64.         ind = siftup(i)
  65.         siftup(ind)
  66. fout.close()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top