우선순위 큐

우선순위 큐

• 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조
• 데이터를 우선순위에 따라 처리하고 싶을 때 사용

 

구현

• 리스트를 이용한 구현
• 힙(heap)을 이용한 구현
• 데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도는 다음과 같음

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

• 리스트의 경우 데이터를 차례대로 넣은 뒤, 우선순위에 맞게 꺼내는 방식
• 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일(힙 정렬)
• 이 경우, 시간 복잡도는 O(NlogN)

 

힙(Heap)의 특징

• 힙은 완전 이진 트리 자료구조의 일종
• 힙에서는 항상 루트 노드를 제거

 

최소 힙(min heap)

• 루트 노드가 가장 작은 값을 가짐
• 값이 작은 데이터가 우선적으로 제거

 

최대 힙(max heap)

• 루트 노드가 가장 큰 값을 가짐
• 따라서 값이 큰 데이터가 우선적으로 제거

 

최소 힙 구성 함수 Min-Heapify()

• (상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체

 

힙의 원소 삽입 삭제

• 힙 자료구조는 기본적으로 완전 이진 트리를 따르기 때문에 균형 잡힌 트리로서 동작
• 원소가 삽입 또는 삭제되었을 때 O(logN)의 시간 복잡도로 힙 성질 유지

원소의 삽입 후 정렬

 

원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 함

원소의 제거

 

이후에 루트 노드에서부터 하향식으로(더 작은 자식 노드로) Heapify()를 진행

원소의 제거 후 정렬