heap 과 python 'heapq' 모듈

📖 우선순위 큐(Priority Queue)

큐(queue)는 알다시피 자료구조 중 하나로, 먼저 넣은 자료가 먼저 나오는 FIFO(First In First Out)구조를 가지고 있다.
우선순위 큐(Priority queue)는 큐와는 달리 우선 순위가 가장 높은 데이터가 먼저 나오는 자료구조이다.
(Ex. 물건들을 넣은 순서대로가 아닌 비싼 물건 순서대로 꺼내야 하는 경우)

이러한 우선순위 큐는 리스트를 통해 구현 하는 방법과 힙(heap)을 통해 구현하는 방법이 있다.
리스트를 통해 구현하는 방식의 시간 복잡도는 삽입할 때 O(1), 삭제할 때 O(N)이고, 힙을 통해 구현하는 방식의 시간 복잡도는 삽입, 삭제 할 때 모두 O(logN)이다.
그래서 힙을 통해 구현하는 것이 더 효율적이다.

🤷‍ 그래서 heap 이란?

힙은 완전 이진 트리 자료구조의 일종으로, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었다.
힙은 부모 노드와 자식 노드의 값들을 비교하며 우선 순위가 더 높은 노드를 루트 노드가 되게 한다.
힙에는 최소힙(Min heap)과 최대힙(Max heap)이 있다.

• 최소 힙 (min heap)
  - 루트 노드가 가장 작은 값을 가진다. -> 최솟값
• 최대 힙 (max heap)
  - 루트 노드가 항상 큰 값을 가진다. -> 최댓값

  최소 힙의 예시

📝 어떻게 구현할까?

구현을 쉽게하기 위해 트리의 첫 번째 인덱스(0)는 사용하지 않는다.
힙에서 부모노드와 자식노드의 관계는 다음과 같다.

• 왼쪽 자식 노드의 인덱스 : (부모 노드의 인덱스) * 2
• 오른쪽 자식 노드의 인덱스 : (부모 노드의 인덱스) * 2 + 1
• 부모 노드의 인덱스 = (자식 노드의 인덱스) / 2

삽입할 때
먼저 값을 맨 마지막에 삽입하고, 부모 노드와 값을 비교해가며 자리를 찾아간다.
예시는 아래와 같다.

2를 추가 했을 때, 맨 마지막에 값을 넣어준다.

부모 노드인 8과 비교 했을 때, 2가 더 작으니 자리를 바꿔준다.

또 다시 부모 노드와 비교하고 값을 바꿔준다.

2를 없애고 마지막 순위의 노드인 8을 루트 노드로 올린다.

이 상태에서 다시 최소 노드를 루트 노드로 올리는 과정을 진행한다.

이 상태에서 다시 최소 노드를 루트 노드로 올리는 과정을 진행한다.

👍 python의 heapq 모듈

파이썬에서는 이러한 힙을 구현해주는 heapq 모듈을 제공한다.

import heapq

위 처럼 선언해주면 heapq를 사용할 수 있다.
사용법은 아래와 같다.

heap = []
heapq.heapify(heap) # 리스트를 힙 구조로 변환
heapq.heappush(heap, item) # 힙에다가 item을 삽입 
heapq.heappop(heap) # 힙에서 루트 노드를 pop하고 리턴 (만약 힙이 비어있는 경우에는 IndexError 호출)