[12주차] 우선순위 큐와 힙

4월 6일 자 학습 내용 정리입니다.

 

 

✅ 우선순위 큐

우선순위 큐는 우선순위가 높은 원소가 먼저 출력되는 추상적 자료형이다.

우선순위 큐를 단순히 배열로 구현할 경우 입력은 O(1)이지만 출력은 O(n)이다.
우선순위가 가장 높은 원소를 찾는 과정과 그 원소를 제거하는 과정이 비효율적이라고 할 수 있다.

 

 

✅ 힙

힙(Heap)은 최솟값 또는 최댓값을 빠르게 찾기 위해 고안된 완전 이진 트리이다.

힙은 최대 힙과 최소 힙의 두 가지 종류로 나뉜다.

최대 힙(Max Heap)은 부모 노드가 항상 자식 노드보다 큰 값을 가지고 있다는 특징이 있다.
반대로 최소 힙(Min Heap)은 부모 노드가 항상 자식 노드보다 작은 값을 가지고 있다는 특징이 있다.

파이썬에서는 heapq 모듈로 최소 힙을 사용할 수 있다.
만약 최대 힙을 사용하고 싶을 경우 힙에 숫자형 자료를 저장할 때 -1을 곱한 값을 저장하면 된다.
-1을 곱함으로서 최댓값과 최솟값이 반전된다는 점을 이용한다.

 

✔️ 자료 입력

힙은 완전 이진 트리의 특성을 유지해야 한다.
따라서 입력된 자료는 항상 마지막 레벨의 가장 오른쪽 자리에 채워진다.
그리고 부모와 값을 비교한 뒤 알맞은 자리를 찾아가는 것이다.

 

이때 최악의 경우는 새로운 최솟값이 입력되는 경우이고 새 노드가 제자리를 찾아가기 위해서는 leaf node에서 root node까지 거슬러 올라가게 된다.
이 경우 발생하는 연산 횟수는 트리의 높이와 비례하므로 O(log n)의 시간복잡도를 가진다.

 

✔️ 자료 출력

힙에서 출력되는 자료는 무조건 루트노드이다.
루트노드가 출력되면 다시 루트 노드를 채워야한다.
이 경우에도 완전 이진 트리의 특성을 유지해야 하기 때문에 마지막 레벨의 가장 오른쪽에 있는 node를 루트 자리에 넣은 뒤 자식들과 값을 비교해 알맞은 자리를 찾아간다.

 

이때 최악의 경우는 힙의 맨 마지막 원소가 가장 큰 값을 가진 경우이다.
이 경우 발생하는 연산 횟수는 트리의 높이와 비례하므로 O(log n)의 시간복잡도를 가진다.