반응형
11279번: 최대 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가
www.acmicpc.net
import sys
def swap(a,b):
tmp = a
a = b
b = tmp
return a, b
def insert_max_heap(heap, x):
child = len(heap)
heap.append(x)
while(True):
parent = child//2
if heap[parent] < heap[child]:
heap[parent], heap[child] = swap(heap[parent], heap[child])
child = parent
else:
break
return heap
def delete_max_heap(heap, x):
item = heap[1]
heap[1] = heap[len(heap)-1]
heap.pop()
parent = 1
while(True):
child = parent*2
if child >= len(heap):
break
elif child+1 < len(heap):
if heap[child] < heap[child+1]:
child += 1
if heap[parent] < heap[child]:
heap[parent], heap[child] = swap(heap[parent], heap[child])
parent = child
else:
break
print(item)
return heap
if __name__ == '__main__':
N = int(sys.stdin.readline())
X = [int(sys.stdin.readline()) for _ in range(N)]
heap = [2**31]
for x in X:
if x == 0:
if len(heap) == 1:
print(0)
else:
heap = delete_max_heap(heap, x)
else:
heap = insert_max_heap(heap, x)반응형