백준 - 11279- 최대힙 [파이썬]

1. 문제

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

11279번: 최대 힙

2. 이해 및 풀이

이 문제를 풀려고 힙 정렬 공부좀 해봐따

https://jjrm.tistory.com/149

[자료구조] 힙 정렬(heap sort)

https://hongjw1938.tistory.com/22

이때 이거 하면서 느낀건 재귀함수 원리를 알아야 한다는 것과(가장 큰/작은 수는 끝까지 인덱스 올려줘야 하니까)

결국 힙정렬은 완전트리에 인덱스를 더한것! (다만 중요한 것은 시작인덱스가 0이면 안됨..대참사남)

 

주워들은 바로는 heapq import해서 쓰면 된다는데, 예쩐에 박필원교수님이 원리를 알고 써야 한다고 해서 안써보고 풀어보겟다는 응꼬집을 부렸다

 

0을 입력하면 최대값을 꺼내야 하고 그 외의 수는 넣어야 하니 push 함수와 pop함수를 썼다.

push를 하면 당연히 맨 마지막 인덱스로 들어간다. 이때 부모 노드보다 크면 (이떄 노드 번호를 tn으로 하면 부모노드는 tn//2) 배열인덱스를 바꿔준다.

pop을 하면 최대값을 뽑아준다. heap_size가 0이면 0을 출력하고 1이면 heap_size번째에 있는 원소를 첫번째 원소로 보낸 후에 출력한다.

import sys
input = sys.stdin.readline

heap = [0]
heap_size = 0

def push(heap, n):
    global heap_size
    # heap의 자리가 부족할 경우 배열을 2배로 늘려나간다.
    if len(heap)-1 == heap_size:
        heap = heap + [0]*len(heap)
    
    heap_size += 1
    heap[heap_size] = n
    
    # 인덱스 부모로 올라가며 탐색하기
    tn = heap_size
    while(tn > 1):
        if heap[tn] > heap[tn//2]:
            temp = heap[tn]
            heap[tn] = heap[tn//2]
            heap[tn//2] = temp
            tn//=2
        else:
            break
    return heap

def pop(heap):
    global heap_size
    if heap_size == 0:
        return 0
    p = heap[1]
    heap[1] = heap[heap_size]
    heap[heap_size] = 0
    
    # 인덱스 자녀로 내려가며 탐색하기
    tn = 1
    while(heap_size > tn*2):
        if heap[tn*2] == 0 and heap[tn*2+1] == 0:
            break
        if heap[tn] < max(heap[tn*2], heap[tn*2+1]):
            temp = heap[tn]
            if heap[tn*2] > heap[tn*2+1]:
                heap[tn] = heap[tn*2]
                heap[tn*2] = temp
                tn *= 2
            else:
                heap[tn] = heap[tn*2+1]
                heap[tn*2+1] = temp
                tn = tn*2+1
        else:
            break
    heap_size -= 1
    return p
    
N=int(sys.stdin.readline())
for i in range(N):
    x = int(input())
    if x ==0:
        print(pop(heap))    
    else:
        heap = push(heap,x)

우영우 보고 올뤠요,,