컴공, 개발자 지인들과 떠들며 장난을 치다 보면 "스택에 쌓아둔다"라는 장난이 종종 나오는데 개발자 지인은 한 발짝 더 나아가 "그래서 큐야 우선순위 큐야?!" 하는 이야기를 한다. 상황이 아니라 감정만 기억에 남아.. 너무 재미없게 이야기를 꺼내 적는 거 같아 속상하지만, 기억이 난다면 추가로 적을 수 있으니. (사실 이야기는 재미없고 분위기가 재밌었는지도 모른다.🙈) 장황하지만, 자료구조를 공부한 지 오래돼서 다 잊은 거 같아 정리하고, 나중에도 훑어볼 수 있게 기록으로 남기려 한다는 말이다!
자료구조와 알고리즘을 따로 분류해서 생각해본 적이 없는 분들이 많은 거 같다. 대학 전공에서도 자료구조와 알고리즘이라는 과목으로 나오기도 하기 때문일까. 둘은 어떤 게 다를까?
-
자료구조는 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조이다.
-
알고리즘은 어떠한 문제를 해결하기 위한 절차나 방법이다.
그렇기에 알고리즘은 문제를 해결하기 위한 절차에 대한 고민이 필요하고, 자료구조와 연산 방법을 선택해 해결한다.
자료구조와 알고리즘이 중요한 이유는 어떤 자료구조와 알고리즘을 쓰냐에 따라 성능이 크게 달라지기 때문이다.
우선순위 큐
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.
| 자료구조 | 추출되는 데이터 |
|---|---|
| 스택(Stack) | 가장 나중에 삽입된 데이터 |
| 큐(Queue) | 가장 먼저 삽입된 데이터 |
| 우선순위 큐(Priority Queue) | 가장 우선순위가 높은 데이터 |
우선순위 큐를 구현하는 방법
- 리스트 이용한 구현
차례대로 데이터 넣은 후 꺼낼 때 리스트에서 각각에 데이터 확인 후 가장 값이 큰 데이터 추출한다. - 힙(heap) 이용한 구현
데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도는 아래와 같다.
| 구현 방식 | 삽입 시간 | 삭제 시간 |
|---|---|---|
| 리스트 | O(1) | O(N) |
| 힙(heap) | O(logN) | O(logN) |
힙(heap)의 특징
- 완전 이진 트리 자료구조의 일종이다.
완전 이진 트리란, 루트 노드부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 삽입되는 트리이다.
- 항상 루트 노드를 제거한다.
- 최소 힙(min heap)
루트 노드가 가장 작은 값을 가진다.- 값이 작은 데이터가 우선 제거된다.
ex. 최소 힙에 데이터를 전부 넣고 꺼내면 오름차순 정렬된 결과 출력
- 값이 작은 데이터가 우선 제거된다.
- 최대 힙(max heap)
루트 노드가 가장 큰 값을 가진다.- 값이 큰 데이터가 우선으로 제거된다.
최소 힙 구성 함수 : Min-Heapify()
-
부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 작은 경우 위치를 교체한다.
새로운 원소가 삽입되면 O(logN)의 시간 복잡도로 힙 성질 유지할 수 있다.
-
원소를 제거할 때 O(lonN)의 시간 복잡도로 힙 성질 유지할 수 있다.
힙 라이브러리를 활용한 우선순위 큐 구현 (python)
import sys
import heapq
n = int(sys.stdin.readline())
arr = [ x for x in range(n)]
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
res = heapsort(arr)
for i in range(n):
print(res[i])python은 힙 자료구조가 min heap 형태로 동작하기에 오름차순 정렬이 수행된다.
max heap 형태로 동작하기를 원한다면, 데이터 넣을 때와 꺼낼 때 - 를 붙이면 가능하다.
