힙은 이진 트리(binary tree)를 응용한 자료구조로 우선순위가 높은 값이 뿌리 노드에 존재하고, 자식 노드로 갈 수록 우선순위가 낮은 값이 존재한다. 모든 원소가 올바른 순서로 정렬돼있지는 않지만 부모 노드는 모든 자식 노드들 보다 우선 순위가 높은 상태를 유지하고 원소가 삭제, 추가 되었을 때도 정렬 상태가 유지된다. 이러한 정렬 상태를 느슨한 정렬상태라고 한다. 모든 원소의 순서보다는 현 시점의 리스트에서 최소값 또는 최대값이 필요한 문제에서 자주 사용된다.

# heap 예시

[1, 2, 3, 5, 4, 6]

      1
     / \
=   2   3
   / \ / \
  5  4 6


새로운 원소가 삽입될시엔, 다음과 같이 부모 노드와의 비교를 통해 순서를 갱신한다.

heapq.heappush([1, 2, 3, 5, 4, 6], 0)

      1                   1                   0
     / \                 / \                 / \
=   2   3       ⇒      2   0       ⇒      2   1
   / \ / \             / \ / \             / \ / \
  5  4 6  0           5  4 6  3           5  4 6  3


파이썬은 내장 모듈에 최소 힙을 구현한 heapq 모듈이 존재해 구현 없이 간편하게 사용할 수 있었다. 다음은 heapq 모듈의 사용 예시이다.

import heapq

array = [2, 1, 3, 5, 4]  # list
heapq.heapify(array)     # list to heap
print(array)

heapq.heappush(array, 6) # push element in heap
print(array)

print(array[0])          # get minimum value without pop    
heapq.heappop(array)     # pop element in heap
print(array)

[1, 2, 3, 5, 4]
[1, 2, 3, 5, 4, 6]
2
[2, 4, 3, 5, 6]


최대 힙은 구현돼있지 않아 조금 다른 방식을 써야 한다. 값이 클 수록 높은 우선순위를 부여하면 되는데, 문제는 우선순위를 부여하기 위해선 정렬을 사용해야 하고, 시간복잡도가 높아져 힙을 구현하는 의미가 없을 것이다. 따라서 개인적으로는 리스트에 -1을 곱하는 방식이 더 간단하고 좋다고 생각된다.

array = [2, 1, 3, 5, 4]
array = list(map(lambda x : -x, array))  # reverse priority
heapq.heapify(array)
print(list(map(lambda x : -x, array)))

[5, 4, 3, 1, 2]