백준 11279번: 최대 힙

문제

• https://www.acmicpc.net/problem/11279
• 최대 힙 구현하기

기록 포인트

• 최대 힙 구현한 내용 기록하기
  • 문제 풀이에 상관 없더라도 관련된 함수들을 함께 기록해 둠

접근 방식

• ITA 책을 참고해 최대 힙 구현

제출 답안

def parent(i):
    return (i-1)//2

def left(i):
    return i*2 + 1

def right(i):
    return i*2 + 2

def heapify(arr, i):
    l, r = left(i), right(i)
    largest = i
    if l < len(arr) and arr[l] > arr[largest]:
        largest = l
    if r < len(arr) and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, largest)

def build_heap(arr):
    parent_end = len(arr)//2 - 1
    for i in range(parent_end, -1, -1):
        heapify(arr, i)

def get_max(heap):
    return heap[0]

def extract_max(heap):
    L = len(heap)
    if L < 1:
        return False
    max_value = heap[0]
    heap[0] = heap[L-1]
    heap.pop()
    heapify(heap, 0)
    return max_value
    
def increase(heap, i, v):
    if v < heap[i]:
        return False
    heap[i] = v
    while i > 0:
        p = parent(i)
        if heap[p] >= heap[i]:
            break
        heap[p], heap[i] = heap[i], heap[p]
        i = p
    
def insert(heap, v):
    heap.append(v)
    i = len(heap) - 1
    while i > 0:
        p = parent(i)
        if heap[p] >= heap[i]:
            break
        heap[p], heap[i] = heap[i], heap[p]
        i = p
        
        
import sys
N = int(sys.stdin.readline())

heap = []
for i in range(N):
    todo = int(sys.stdin.readline())
    if todo == 0:
        # 힙에서 가장 큰 값을 출력
        v = extract_max(heap)
        print(v or 0)
    else:
        # 힙에 자연수 추가
        insert(heap, todo)