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

우선순위 큐 (Priority Queue)

: 우선순위가 높은 데이터가 먼저 반환되는 자료구조

 

 

• 힙으로 구현

배열, 리스트 : 삽입 시 모든 데이터 탐색해야 하므로 시간복잡도 O(n)

힙 : 삭제, 삽입 시 부모-자식 비교 반복 → 트리의 높이가 하나 증가할 때마다 비교 연산 횟수는 1회 증가하여 시간복잡도 O(logn)

 

 

 

 

힙 (Heap)

 

• 특징

완전이진트리
모든 노드에 저장된 값(우선순위)들은 자식 노드들 값보다 크거나 같음

루트노드가 가장 큰 우선순위를 가짐

 

힙을 구현하는 일반적인 자료구조 => 배열

 

 

 

• 종류

• 최대 힙

값이 클수록 우선순위가 높은 완전이진트리

 

 

 

• 최소 힙

값이 작을수록 우선순위가 높은 완전이진트리

 

 

 

• 구현

• 삽입(저장)

새 노드를 우선순위가 가장 낮다는 가정으로 맨 끝 위치에 삽입시킨 후 부모노드와 비교해가며 제자리로 위치시킴 (=heapify)

 

 

 

 

• 삭제

1. 우선순위가 가장 높은 데이터를 pop함

2. 마지막 노드를 루트노드에 대입한 후, 자식노드들과 비교하며 제자리로 위치시킴

 

 

 

 

 

참고

https://chanhuiseok.github.io/posts/ds-4/

https://st-lab.tistory.com/219