자료구조: 우선순위 큐(Priority Queue) 와 힙(Heap)

우선순위 큐

- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

- 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.

ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인하는 경우

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

 

우선순위 큐 구현 방법

1) 리스트를 이용하여 구현

2) 힙(heap)을 이용하여 구현

 

데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도

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

단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일함

- 힙정렬: 힙에 넣으면 우선순위에 따라 정렬 됨

- 이 경우 시간 복잡도는 O(NlogN)

 

힙(Heap)

• 완전 이진 트리 자료구조의 일종
• 항상 루트노드(root node)를 제거함
• 최소 힙(min heap)
  • 루트 노드가 가장 작은 값
  • 값이 작은 데이터가 우선적으로 제거됨
• 최대 힙(max heap)
  • 루트 노드가 가장 큰 값
  • 값이 큰 데이터가 우선적으로 제거됨

 

완전 이진트리(Complete Binary Tree)

- 루트(node)부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)를 의미

완전 이진 트리

 

 

 

 

 

 

 

 

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

• (상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치 교체
• 새로운 원소가 삽입 되었을 때, 원소가 제거 되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지
• 원소 삽입 시 가장 아래 노드에 추가 되었다가 부모와 자신의 값을 비교하여 자신의 값이 더 작은 경우에 위치 교체
• 원소가 제거 되었을 때 가장 마지막 노드가 루트이 노드 위치에 오도록 하고 이후 루트 노드에서 부터 하향식으로(더 작은 자식 노드로) Heapify()진행

 

 

본 글은 동빈나의 자료구조: 우선순위 큐(Priority Queue) 와 힙(Heap) 강의를 토대로 정리한 내용입니다.