[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap)이란?

우선순위 큐란?

• 일반적인 큐(Queue)에서는 먼저 들어간 데이터가 제일 먼저 나오는 FIFO(First In First Out) 형태로 이루어진 선형 자료구조이다.
• 우선순위 큐는 이러한 FIFO 형식이 아닌 우선순위를 매겨 우선순위가 가장 높은 데이터가 먼저 나오는 것을 말한다.

우선순위 큐 특징

1. 모든 데이터에는 우선순위를 가지고 있다.
2. 우선순위가 가장 높은 데이터가 먼저 queue에서 나오게 된다.
3. 데이터의 우선순위가 같은 경우에는 먼저 queue에 들어온 데이터가 높은 우선순위를 가지게 됩니다.

우선순위 큐 구현방법

1. 리스트 기반
2. 연결 리스트
3. 힙 기반

리스트의 경우에는 데이터가 많아질 경우 우선순위에 따라 모두 비교한 다음, 해당 위치 뒤부터 전체 데이터를 뒤로 밀어줘야 한다.

 

연결리스트의 경우에는 리스트와 같이 노드 간의 연결을 거쳐 모든 노드에 접근하고 비교를 해야한다.

힙이란?

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 여러 개의 데이터 중에서 최댓값 또는 최솟값을 빠르게 찾기 위해 만들어진 자료구조이다.
• 이진 탐색 트리와는 다르게 중복된 값을 허용한다.

힙의 종류

최대 힙(Max Heap)

• 루트 노드가 가장 큰 값을 가짐
• 우선순위에 의해 가장 큰 값이 먼저 제거된다.

최소 힙(Min Heap)

• 루트 노드가 가장 작은 값을 가짐
• 우선순위에 의해 가장 작은 값이 먼저 제거된다.

힙의 삽입

• 힙의 삽입은 가장 마지막 노드에 추가되어, 부모노드를 비교하여 위치를 교체하면서 올라가는 식이다. (상향식)

추가된 노드인 5와 부모 노드인 6을 비교를 해 위치를 바꾼다.

힙의 삭제

• 힙의 삭제는 루트 노드를 삭제 후 가장 마지막 노드가 루트 노드로 와 재정렬 하는 형식이다.
• 만약 자식 노드 둘 다 부모 노드보다 낮은 경우 더 낮은 자식 노드로 이동

1이 삭제되고, 마지막 노드인 6이 루트 노드로 이동

루트 노드에서 최소 힙 성질이 만족할 때까지 자식 노드와 비교하며 이동

최종적인 형태

힙의 부모 또는 자식 노드 찾기

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

우선순위 큐 시간 복잡도

우선 순위 큐를 구현하는 방법	삽입 시간 복잡도	삭제 시간 복잡도
순서 없는 배열	O(1)	O(n)
순서 없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(n)	O(1)
힙(heap)	O(logn)	O(logn)