우선순위 큐(Priority Queue)와 힙(Heap)

우선순위 큐 (Priority Queue)

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

Stack vs Queue vs Priority Queue

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

 

구현방법

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

• 리스트의 경우 삭제할 때 가장 높은 우선순위를 가지는 데이터를 찾기 위해서 선형적인 탐색 시간 소요됨
  
  
• 단순히 N 개의 데이터를 힙에 넣었다가 모두 꺼내는 작업만 수행하더라도 그 자체로 정렬이 수행됨
• 시간복잡도는 O(NlogN)

 

힙 (Heap)

• 완전 이진 트리 자료구조의 일종
• 항상 루트 노드를 제거한다.
• 최소힙
  - 루트 노드가 가장 작은 값을 가짐
  - 값이 작은 데이터가 우선적으로 제거됨
• 최대힙
  - 루트 노드가 가장 큰 값을 가짐
  - 값이 큰 데이터가 우선적으로 제거됨

 

완전 이진 트리 (Complete Binary Tree)

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

 

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

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

- 새로운 원소가 삽입되었을 때 / 원소가 제거되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

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

   - 이후에 루트 노드에서부터 하향식으로 Heapify()를 진행한다.

 

 

 

▶ Programmers 우선순위 큐 문제 (내가 푼 문제들 중)

https://coding-hana.tistory.com/72

[프로그래머스_JS] Lv.3 [1차] 셔틀버스(17678)

https://coding-hana.tistory.com/75

[프로그래머스_JS] Lv.3 야근 지수(12927)

 

 

 

### 참고한 강의

https://www.youtube.com/watch?v=AjFlp951nz0