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_42.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)
        
'''
출력:
6
5
5

'''

 

input_42.txt(입력)

5
3
6
0
5
0
2
4
0
-1

 

 

중요내용

1. 최대힙은 부모노드가 모든 자식노드보다 항상 큰 값을 가져야 한다.
2. 따라서 최대힙 구조에서는 루트노드에 최대 값이 들어가 있다.
3. 기본적으로 최대힙 구조는 최소힙 구조와 정 반대의 원리일 뿐, 노드에 데이터가 배열되는 원리는 비슷하다.
4. heapq는 기본적으로 최소힙의 원리로 데이터를 배열한다.
5. 따라서 최대힙 구조를 만들기 위해서는 리스트에 데이터를 삽입하고 추출하는 과정에서 해당 데이터의 부호를 (-)로 바꿔줘야 한다.
6. 즉, hq.heappush(a, -n)의 코드처럼 리스트 a에 데이터를 넣을 때 부호를 바꿔주면 자동으로 최대힙 구조로 데이터가 배열된다.
7. 그 이후, -hq.heappop(a)의 코드처럼 해당 데이터의 부호를 원래대로 돌려놓기 위해서는 (-) 부호를 붙여서 데이터를 출력해야 한다.
8. 참고로, print(-hq.heappop(a))코드는 루트노드 값을 추출할 때 해당 값에 (-)를 붙여서 추출한 후 출력하는 것을 의미한다.