Baekjoon 11279번 최대 힙

문제

https://www.acmicpc.net/problem/11279

걸린 시간

00 : 40 : 53

풀이

Python3

import sys
input = sys.stdin.readline

class maxHeap():
    def __init__(self, max_size):
        self.heap_size = 0
        self.heap = [None] * max_size

    def is_empty(self):
        if self.heap_size == 0:
            return True
        else:
            return False

    def insert(self, item):
        self.heap_size += 1    
        i = self.heap_size

        while i != 1 and self.heap[i//2] < item:
            self.heap[i] = self.heap[i//2]
            i = i//2

        self.heap[i] = item    

    def delete(self):
        if self.is_empty():
            return 0
        else:
            item = self.heap[1]
            temp = self.heap[self.heap_size]
            self.heap_size -= 1

            parent = 1
            child = 2

            while child <= self.heap_size:
                if child < self.heap_size and self.heap[child] < self.heap[child+1]:
                    child += 1

                if temp > self.heap[child]:
                    break

                self.heap[parent] = self.heap[child]
                parent = child
                child *= 2

            self.heap[parent] = temp
            return item

if __name__ == "__main__":
    maxH = maxHeap(100000) # 최대 힙
    result = []

    N = int(input().strip())

    for _ in range(0, N):
        tmp = int(input().strip())
        if tmp == 0:
            result.append(maxH.delete())
        else:
            maxH.insert(tmp)

    for i in result:
        print(i)

삭제연산의 알고리즘 구현이 매우 헷갈렸다.