Algorithm - 최소힙

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[최소힙]

 

최소힙은 완전이진트리로 구현된 자료구조 이다.

 

그 구성은 부모 노드값이 왼쪽자식과 오른쪽자식 노드 값보다 작게 트리룰 구성하는 것이다.

그렇게 하면 트리의 루트(root)노드에는 입력된 값들 중 가장 작은 값이 저장된다.

예를 들어, 5 3 2 1 4 6 7순으로 입력되면 최소힙 트리는 아래와 같이 구성된다.

 

최소힙 트리

 

최소힙 자료를 이용하여 다음의 연산을 하는 프로그램을 작성하시오.

1. 자연수가 입력되면 최소힙에 입력한다.
2. 숫자 0이 입력되면 최소힙에서 최소값을 꺼내어 출력한다. (단, 출력할 자료가 없으면 -1을 출력함)
3. -1이 입력되면 프로그램을 종료한다.

 

 

*입력 설명

첫 번째 줄부터 숫자가 입력된다. 

입력되는 숫자는 100,000개 이하이며 각 숫자의 크기는 정수형 범위에 있다.

 

*출력 설명

연산을 한 결과를 보여준다.

 

 

---

 

 

풀이(Python)

답안

import sys
import heapq as hq
sys.stdin = open('AA/input_41.txt', 'rt')

a = []
while True:
    n = int(input())
    if n == -1:
        break
    if n == 0:
        if len(a) == 0:
            print(-1)
        else:
            print(hq.heappop(a))
    else:
        hq.heappush(a, n)
        
'''
출력:
3
5
2

'''

 

input_41.txt(입력)

5
3
6
0
5
0
2
4
0
-1

 

 

중요내용

1. 같은 레벨의 노드에 데이터를 채울 경우, 반드시 왼쪽 노드부터 데이터를 넣는다.
2. 부모 노드가 자식 노드보다 크면, 두 노드를 스왑하여 최소힙 조건을 만족시킨다.
3. 즉, 노드의 데이터를 채울 때에는 레벨 순으로 왼쪽부터 채우며 입력된 노드 값들은 최소힙 조건을 만족시키기 위해 서로 스왑된다.
4. 최소힙 구조에서 데이터를 추출하고 삽입할 때에는 heappop() 함수와 heappush() 함수를 사용한다.
5. 일반적으로 최소힙 구조를 완성하면 heappop() 함수를 통해 루트노드 값을 추출하고, 최소힙에서 가장 낮은 레벨의 맨 우측 노드 값을 루트노드 값으로 넣어준다. 그 이후 다시 최소힙 구조를 완성시키기 위해 노드 간 스왑을 진행한다. (이러한 과정을 다운힙 과정이라고 함)
6. 만약, 최소힙 구조에 노드 값을 삽입하면 업힙을 통해 최소힙 구조를 완성시키고 반대로 노드 값을 추출하면 다운힙을 통해 최소힙 구조를 완성시킨다.
7. 기본적으로 heapq 자료구조는 최소힙 구조로 데이터를 배열한다.
8. hq.heappop(a) 함수는 리스트 a에서 루트노드 값을 추출하는 코드이다.
9. hq.heappush(a, n) 함수는 리스트 a에 최소힙(완전이진트리)의 구조로 n 값을 넣어주는 코드이다.