[자료구조] 우선순위 큐와 힙

우선순위 큐

우선순위 큐는 일반적인 큐와 다르게 우선 순위가 높은 요소가 먼저 나가는 개념이다.

여기서 주의할 점은 우선순위 큐는 자료구조가 아닌 개념이다.
따라서 우선순위 큐를 구현하는 방법은 다양하게 존재할 수 있다.

그중 힙은 우선순위 큐를 구현하기 위한 가장 적합한 방법이다.

 

 

힙 (Heap)

힙은 자료구조이며, 이진 트리 형태이다. 우선순위가 높은 요소를 루트에 두기위해 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있다.

위 예시에서는 값이 클수록 우선순위가 높고, 6이 가장크므로 루트에 있다.

 

힙의 특징

• 우선순위가 가장 높은 것을 루투에 두고, 항상 루트가 먼저 나간다.
• 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙 두가지로 나뉜다. (오름차순이냐 내림차순이냐 정도의 차이)
• 파이썬에서는 heapq 혹은 PriorityQueue 모듈을 통해서 쉽게 힙을 구현할 수 있다.
• 요소 추가 시, 항상 이진 트리의 마지막에 추가되기 때문에 힙은 항상 완전 이진 트리다.

 

 

힙 추가 알고리즘

1. 이진 트리의 가장 마지막에 추가한다.

2. 요소가 추가되었다면 부모 정점보다 우선순위가 높은지 체크한다.

3. 만약 추가된 요소가 더 높다면 부모와 바꾼다.

4. 더이상 순서를 바꿀수 없을 때까지 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.

5. 따라서 높이는 log N이기에 요소 추가 알고리즘은 최악의 경우에도 log N이다.  (O(logN) 시간복잡도를 가진다)

 

최대 힙 예시

1. 45라는 요소 추가 -> 루트에 45 정점이 생김

2. 36 요소를 추가. 이진트리이므로 루트의 왼쪽에 추가된다.

3. 54 요소를 추가. 이진트리이므로 루트의 오른쪽에 추가된다.

4. 최대 힙에서 45보다 54가 우선순위가 더 높기 때문에 서로 순서를 바꾼다. 마찬가지로 배열도 바뀐다.

5. 이번엔 27을 추가. 마지막 위치인 36의 왼쪽 정점에 추가된다.

6. 다음으로 63을 추가. 36의 오른쪽 정점에 추가된다.

7. 이 상태에서 36보다 63이 우선순위가 더 높기 때문에 바꿔야한다.

8. 여기서 또 다시 부모 정점과 비교하면 54보다 63이 우선순위가 더 높다. 따라서 둘의 위치를 바꾼다.

9. 루트까지 이동했기 때문에 탐색을 종료한다. 이렇게 최대 힙이 완성된다.

 

 

 

힙 제거 알고리즘

1. 먼저 요소를 제거하는건 루트만 가능하다.

2. 루트 정점이 제거되면 그 공백을 가장 마지막 정점이 대체한다.

3. 이때 추가와는 반대로 루트로부터 점점 정점을 아래로 내려야한다.

4. 루트 정점의 두 자식 정점 중, 더 우선 순위가 높은 정점과 바꾼다.

5. 두 자식의 정점이 더 우선순위가 낮을 때까지 반복한다.

6. 그러면 자연스럽게 우선 순위가 더 높은 정점이 루트 정점이 될 수 있다.

7. 추가와 마찬가지로 제거도 완전 이진 트리의 높이만큼만 진행되기에 시간복잡도가 O(logN)(==로그시간)을 가진다.

 

 

힙 제거 예시

1. 루트정점인 63을 제거

2. 63이 제거되면 가장 마지막 정점인 36이 루트에 위치하게됩니다.

4. 여기서 36의 자식 정점인 54와 45를 비교

5. 54가 우선순위가 더 높기 때문에 36과 54를 바꾼다

6. 여기서 36의 자식 정점인 27과 비교한다. 오른쪽 자식은 없기 때문에 27하고만 비교하면 된다.

7. 자식의 우선 순위가 더 낮기 때문에 바꾸지않고 로직을 마친다.

 

 

 

파이썬에서 힙 구현

파이썬에서 가장 쉽게 힙을 구현하는 방법은 heapq 모듈을 이용하는 것이다.

heapq 모듈은 기존 리스트 객체를 힙 알고리즘을 사용할 수 있도록 도와주는 모듈이다.

힙에 요소를 추가할 때는 heappush 함수를 이용하고, 힙에서 요소를 제거할 때는 heappop 함수를 사용하면 된다.

아쉬운 점은 heapq는 min heap만 제공한다는 점이다. max heap을 이용하고 싶다면 직접 구현하거나 비 표준 함수를 사용하면 된다.

import heapq

hq = []  # Min heap

# 힙에 요소 추가
heapq.heappush(hq, 45)
heapq.heappush(hq, 36)
heapq.heappush(hq, 54)
heapq.heappush(hq, 27)
heapq.heappush(hq, 63)

print(hq)
>> 27, 36, 45, 54, 63

# 힙에서 요소 제거
print(heapq.heappop(hq))
>> 27
print(heapq.heappop(hq))
>> 36
print(heapq.heappop(hq))
>> 45

# 요소 제거 후 추가
heapq.heapreplace(hq, 10)
print(hq[0])
>> 10

# 요소 추가 후 제거
heapq.heappushpop(hq, 5)
print(hq[0])
>> 10


# 리스트를 힙으로 변경
lst = [5, 1, 2, 7, 4, 9, 8, 10, 3, 6]
heapify(lst)
print(lst)
>> [1, 3, 2, 5, 4, 9, 8, 10, 7, 6]  # Heap 기준에서 바라볼 때 정렬된 모습