힙(Heap) 자료구조 알아보기

힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위하여 사용하는 자료구조 중 하나다. 

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다. 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 설정한다.

우선순위 큐를 구현할 때는 내부적으로 최소 힙(min heap) 또는 최대 힙(max heap)을 이용한다. 최소 힙은 '값이 낮은 데이터가 먼저 삭제'되며, 최대 힙은 '값이 큰 데이터가 먼저 삭제'된다.

파이썬의 힙은 최소 힙으로 구성되어 있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도가 $O(NlogN)$에 오름차순 정렬이 완료된다.

데이터 개수가 N개일 때, 삽입 시 $O(logN)$의 연산을 N번 반복하므로 $O(NlogN)$이고, 삭제할 때도 $O(logN)$의 연산을 N번 반복하므로 $O(NlogN)$이다. 따라서 전체 연산 횟수는 대략 $2Nlog_2N$으로 빅오 표기법에 따라 전체 시간 복잡도는 $O(NlogN)$이 될 것이다.

최소 힙을 최대 힙처럼 사용하기 위해 일부러 우선순위에 해당하는 값에 음수 부호를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 뒤 다시 음수 번호를 붙여 원래 값으로 돌리는 방식을 사용한다.

# PriorityQueue보다 heapq이 더 빠름
# 최소 힙 방식(파이썬 기본 설정)
import heapq

def heapsort(iterable):
  h = []
  result = []
  # 모든 원소를 차례대로 힙에 삽입
  for value in iterable:
    heapq.heappush(h, value)
  # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
  for i in range(len(h)):
    result.append(heapq.heappop(h))
  
  return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

# 최대 힙 방식
import heapq

def heapsort(iterable):
  h = []
  result = []

  # 모든 원소를 차례대로 힙에 삽입
  for value in iterable:
    heapq.heappush(h, -value) # 음수 처리
  # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
  for i in range(len(h)):
    result.append(-heapq.heappop(h))
  return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

해당 코드는 '이것이 취업을 위한 코딩 테스트다'를 참고했습니다.