SHARE
TWEET

Untitled

a guest Jan 21st, 2020 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. SM
  2.  
  3. from typing import List, Any
  4.  
  5.  
  6. def sift_up(heap: List[Any], pos: int) -> None:
  7.     par = (pos - 1) // 2
  8.     while par >= 0:
  9.         if heap[par] < heap[pos]:
  10.             heap[par], heap[pos] = heap[pos], heap[par]
  11.         else:
  12.             return None
  13.         pos, par = par, (par - 1) // 2
  14.  
  15.  
  16. def sift_down(heap: List[Any], length: int) -> None:
  17.     pos = 0
  18.     while pos * 2 + 1 < length:
  19.         if pos * 2 + 2 < length and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
  20.             child = pos * 2 + 2
  21.         else:
  22.             child = pos * 2 + 1
  23.         if heap[child] > heap[pos]:
  24.             heap[child], heap[pos] = heap[pos], heap[child]
  25.         pos = child
  26.  
  27.  
  28. def heap_sort(arr: List[Any]) -> List[Any]:
  29.     heap = []
  30.     for i in range(len(arr)):
  31.         heap.append(arr[i])
  32.         sift_up(heap, i - 1)
  33.     heap_len = len(heap)
  34.     while heap_len > 1:
  35.         if heap[heap_len - 1] < heap[0]:
  36.             heap[heap_len - 1], heap[0] = heap[0], heap[heap_len - 1]
  37.         heap_len -= 1
  38.         sift_down(heap, heap_len)
  39.     return heap
  40.  
  41.  
  42. A = list(map(int, input().split()))
  43. print(' '.join(map(str, heap_sort(A))))
  44.  
  45.  
  46. SN
  47.  
  48. from typing import List, Any
  49.  
  50.  
  51. def sift_up(heap: List[Any], pos: int) -> int:
  52.     par = (pos - 1) // 2
  53.     while par >= 0:
  54.         if heap[par] < heap[pos]:
  55.             heap[par], heap[pos] = heap[pos], heap[par]
  56.         else:
  57.             return pos
  58.         pos, par = par, (par - 1) // 2
  59.     return pos
  60.  
  61.  
  62. def sift_down(heap: List[Any], length: int) -> None:
  63.     pos = 0
  64.     while pos * 2 + 1 < length:
  65.         if pos * 2 + 2 < length and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
  66.             child = pos * 2 + 2
  67.         else:
  68.             child = pos * 2 + 1
  69.         if heap[child] > heap[pos]:
  70.             heap[child], heap[pos] = heap[pos], heap[child]
  71.         pos = child
  72.  
  73.  
  74. n = int(input())
  75. A = list(map(int, input().split()))
  76. for j in range(int(input())):
  77.     i, x = map(int, input().split())
  78.     A[i] += x
  79.     print(sift_up(A, i))
  80. print(' '.join(map(str, A)))
  81.  
  82.  
  83. SO
  84.  
  85. from typing import List, Any
  86.  
  87.  
  88. def sift_up(heap: List[Any], pos: int) -> int:
  89.     par = (pos - 1) // 2
  90.     while par >= 0:
  91.         if heap[par] < heap[pos]:
  92.             heap[par], heap[pos] = heap[pos], heap[par]
  93.         else:
  94.             return pos
  95.         pos, par = par, (par - 1) // 2
  96.     return pos
  97.  
  98.  
  99. def sift_down(heap: List[Any], pos: int) -> int:
  100.     ans = pos
  101.     while pos * 2 + 1 < len(heap):
  102.         if pos * 2 + 2 < len(heap) and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
  103.             child = pos * 2 + 2
  104.         else:
  105.             child = pos * 2 + 1
  106.         if heap[child] > heap[pos]:
  107.             heap[child], heap[pos] = heap[pos], heap[child]
  108.             ans = child
  109.         pos = child
  110.     return ans
  111.  
  112.  
  113. n = int(input())
  114. A = list(map(int, input().split()))
  115. for j in range(int(input())):
  116.     i, x = map(int, input().split())
  117.     A[i] -= x
  118.     print(sift_down(A, i))
  119. print(' '.join(map(str, A)))
  120.  
  121. SP
  122.  
  123.  
  124. from typing import List, Any
  125.  
  126.  
  127. def sift_up(heap: List[Any], pos: int) -> int:
  128.     par = (pos - 1) // 2
  129.     while par >= 0:
  130.         if heap[par] < heap[pos]:
  131.             heap[par], heap[pos] = heap[pos], heap[par]
  132.         else:
  133.             return pos
  134.         pos, par = par, (par - 1) // 2
  135.     return pos
  136.  
  137.  
  138. def sift_down(heap: List[Any]) -> int:
  139.     ans = pos = 0
  140.     while pos * 2 + 1 < len(heap):
  141.         if pos * 2 + 2 < len(heap) and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
  142.             child = pos * 2 + 2
  143.         else:
  144.             child = pos * 2 + 1
  145.         if heap[child] > heap[pos]:
  146.             heap[child], heap[pos] = heap[pos], heap[child]
  147.             ans = child
  148.         pos = child
  149.     return ans
  150.  
  151.  
  152. def insert(heap: List[int], x: int) -> int:
  153.     if len(heap) == n:
  154.         return -1
  155.     heap.append(x)
  156.     return sift_up(heap, len(heap) - 1)
  157.  
  158.  
  159. def extract(heap: List[int]) -> List[Any]:
  160.     if len(heap):
  161.         heap[-1], heap[0] = heap[0], heap[-1]
  162.         ans = heap.pop()
  163.         return [sift_down(heap), ans]
  164.     return [-1]
  165.  
  166.  
  167. n, m = map(int, input().split())
  168. queue = []  # type: List[int]
  169. for j in range(m):
  170.     r = list(map(int, input().split()))
  171.     if r[0] == 1:
  172.         print(*extract(queue))
  173.     else:
  174.         print(insert(queue, r[1]))
  175. print(' '.join(map(str, queue)))
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