1. 힙(heap)

이진 트리는 위의 그림과 같이 부모 노드와 왼쪽 자식 그리고 오른쪽 자식 노드를 가지는 형태인데, 이진 트리 중에서 힙(heap)은 최솟값과 최댓값을 빠르게 그리고 연산횟수가 최소화해서 찾아내기 위해 만들어진 완전 이진트리로 구현된 자료구조이다. 위의 그림은 level이 3인 이진 트리인데, 그림과 같이 마지막 레벨(level 3)을 제외한 나머지 레벨이 완전히 채워져있는 트리를 완전 이진 트리라고 한다. 그리고 노드가 가지는 데이터는 '부모 -> 왼쪽 자식 -> 오른쪽 자식' 노드의 순서로 위에서부터 차례로 채워진다. 하지만 입력된 순서에 따라서 노드에 채워지는 수는 변경될 수 있지만, 현재 자식 노드의 직계 부모보다 자식의 수가 클 수는 없다. 그래프에서 볼 때, level 1의 노드인 2, 3이 그 자리를 바꿔도 완전 이진트리이며 입력 순서에 따라 그 자리 배치는 달라질 수 있다.
stack이나 queue처럼 입력과 출력의 순서에 따라서 데이터를 처리하는 것이 아닌, 입력된 값의 순서와는 상관없이 출력하려는 '값'이 최소인지 최대인지에 따라 출력이 이루어지는 알고리즘이 힙 자료구조이다. 파이썬에서는 heapq 모듈을 import하여 쉽게 사용이 가능하다. 완전 이진 트리를 이용한 heqp 모듈의 작동 방식은 연결 리스트로 이루어져 있어 모든 데이트를 하나하나 찾는 것이 아닌 완전 이진 트리를 이용하여 구동된다. 이런 방식의 빅오 표기법 시간 복잡도는 O(logN)으로 O(N)인 선형 탐색보다 빠르다는 장점이 있다. 힙 자료구조의 삽입과 정렬 그리고 출력에 대해서 자세한 설명보다는 힙을 통해 어떻게 알고리즘 문제풀이에 응용한지 살펴보겠다.

2. 최소힙

기본적으로 힙 자료구조는 최소힙으로써 heap이 가지고 있는 값 중 가장 작은 값을 먼저 출력하도록 제일 위의 노드(root node)는 항상 제일 작은 값이 저장되어 있다.(부모 노드가 항상 자식 노드보다 값이 작다) 큐(Queue)와는 달리 우선 순위가 높은 데이터 값이 출력되는 우선순위 큐(Priority Queue)의 자료구조다.

3. 최대힙

같은 말을 반복하는 것인데, 힙의 자료구조는 최소힙으로 작동되기에 약간의 아이디어만으로 최대힙을 적용할 수 있다. 최대힙을 적용해야 할 때는 값을 입력할 때 마이너스('-') 부호를 붙여서 입력하고 출력할 때 마이너스('-')를 붙여서 출력하는 식으로 최대힙을 구현한다. 마이너스 부호를 붙여 넣으면 제일 큰 값은 자연히 가장 작은 값이 될 것이고 출력할 때 다시 마이너스를 붙여서 원래의 가장 큰 값으로 출력되게 한다.

4.1 문제

숫자 카드 n개가 리스트로 주어진다. 순서대로 n개의 카드를 꺼낼 때 숫자가 0이면 상자에서 가장 작은 값의 숫자 카드를 꺼내고 0이 아닌 숫자 카드가 나오면 상자에 넣었을 때, 상자안에 남아있는 카드의 숫자를 작은 카드 순서대로 모두 출력하시오. 단, 같은 수의 카드는 없다.(2 < n < 1,000)

4.2 풀이

힙에 자료 입력은, heapq.heapqpush(a, b)는 'a'에 'b'를 입력
힙에서 자료 출력은, heqpq.heappop(a)는 'a'에서 출력(출력된 값은 가장 작은 값)

import heapq #힙 자료구조인 heapq모듀 받는다.
def solution(n):
    for i in n:
        if i == 0:
            heapq.heappop(box)# box에서 가장 작은 수를 빼낸다.
        else:
            heapq.heappush(box, i)# box에 i를 삽입한다.
    else:
        while len(box) != 0: # 상자에 남아있는 숫자카크 모두를 꺼낸다.
            print(heapq.heappop(box), end=' ')
n = [5, 6, 3, 0, 1, 14, 0, 9, 7, 12, 0]# 입력값
box = [] # 힙에 사용할 자료구조는 리스트로 활용한다.
solution(n)# 함수 호출
출력: 
6 7 9 12 14