우선순위 큐(Priority Queue)

 

 

www.youtube.com/watch?v=AjFlp951nz0&list=WL&index=26

 

 

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

 

구현 방법

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

그냥 차례대로 쭉 넣은 다음에 꺼낼 때 하나하나 확인해서 값이 큰 거 출력 

2) 힙을 이용하여 구현

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

 

	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

 

• 힙은 완전 이진 트리 자료구조의 일종
  • 루트 노드로부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리
• 힙에서는 항상 루트 노드를 제거한다.
• 최소 힙(Min Heap)
  
  • 루트 노드가 가장 작은 값을 가진다.
  • 따라서 값이 작은 데이터가 우선적으로 제거된다.
• 최대 힙(Max Heap)
  • 루트 노드가 가장 큰 값을 가진다.
  • 따라서 값이 큰 데이터가 우선적으로 제거된다

 

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

• (상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다.
• 힙에서 원소가 제거될 때(루트)
  • 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다. 
  • 이후 루트 노드에서부터 하향식으로(더 작은 자식 노드로) Heapify()를 진행한다.