우선순위 큐와 힙

우선순위 큐 (Priority Queue)

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

우선순위 큐는 데이터를 우선순위데 따라 처리하고 싶을 떄 사용합니다.

구현하는 방법은 1) 리스트 2) 힙(heap)이 있습니다.

단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일합니다. (힙 정렬)
이 경우 시간 복잡도는 O(NlogN)입니다

힙(Heap)의 특징

힙은 완전 이진 트리 자료구조의 일종입니다.
힙에서는 항상 루트 노드 (root node)를 제거합니다.

• 최소 힙(min heap)

  • 루트 노드가 가장 작은 값을 가진다.
  • 따라서 값이 작은 데이터가 우선적으로 제거된다

• 최대 힙(max heap)

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

완전 이진 트리란 루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리를 의미한다.

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

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