5177. [파이썬 S/W 문제해결 기본] 8일차 - 이진 힙
풀이
class MinimumHeap:
def __init__(self, N):
self.heap = [0] * (N+1)
self.idx = 0
def isReversed(self, pidx, cidx):
# pidx : parent index, cidx = child index
if (0 < pidx <= self.idx) and (0 < cidx <= self.idx):
if self.heap[pidx] > self.heap[cidx]:
return True
return False
def swap(self, pidx, cidx):
# pidx : parent index, cidx = child index
self.heap[pidx], self.heap[cidx] = self.heap[cidx], self.heap[pidx]
def insert(self, n):
self.idx += 1
self.heap[self.idx] = n
idx = self.idx
check = self.isReversed(idx//2, idx)
while check:
self.swap(idx//2, idx)
idx = idx//2
check = self.isReversed(idx//2, idx)
def delete(self):
if self.idx > 0:
self.heap[self.idx], self.heap[1] = self.heap[1], self.heap[self.idx]
self.idx -= 1
idx = 1
check = True
while check:
if self.isReversed(idx, idx*2) and self.isReversed(idx, (idx*2)+1):
if self.heap[idx*2] < self.heap[(idx*2)+1]:
self.swap(idx, idx*2)
else:
self.swap(idx, (idx*2)+1)
elif self.isReversed(idx, idx*2):
self.swap(idx, idx*2)
elif self.isReversed(idx, (idx*2)+1):
self.swap(idx, (idx*2)+1)
else:
check = False
def anscestor(self):
result = []
idx = self.idx // 2
while idx > 0:
result.append(self.heap[idx])
idx = idx // 2
return result
T = int(input())
answer = []
for tc in range(1, T + 1):
N = int(input())
mh = MinimumHeap(N)
for i in list(map(int, input().split())):
mh.insert(i)
result = sum(mh.anscestor())
answer.append(result)
for tc in range(1, T+1):
print(f'#{tc} {answer[tc-1]}')