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

1. 우선순위 큐의 정의

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.

2. 우선순위 큐 구현 방법

1) 리스트로 구현
2) 힙(Heap)으로 구현

• 데이터의 개수가 N개일 때 시간 복잡도 차이
  

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

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

❗완전 이진 트리

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

3. 힙(Heap)

• 완전 이진 트리 자료구조의 일종

• 힙에서는 항상 루트 노드(부모가 없는 노드)를 제거한다.

• 최소 힙 (min heap)

  • 루트 노드가 가장 작은 값을 가진다.
  • 값이 작은 데이터가 우선적으로 제거된다.
  • 최소 힙의 구성 함수 : Min-Heapify()
    • 최하위 노드부터 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 부모와 위치를 교환
      

• 최대 힙 (max heap)

  • 루트 노드가 가장 큰 값을 가진다.
  • 값이 큰 데이터가 우선적으로 제거된다.
  • 최대 힙의 구성 함수 : Max-Heapify()
    • 자식이 존재하는 가장 하위 노드부터 거슬러 올라가며, 두 자식 노드 중 더 큰 쪽이 부모 노드의 값보다 큰 경우에 해당 노드를 부모와 교환
      

• 힙에 새로운 원소가 삽입될 때 O(logN)의 시간 복잡도로 힙 성질을 유지

  • 새로 들어온 노드에서부터 상향식으로 Heapify()를 진행한다.
    

• 힙에서 원소가 제거될 때도 O(logN)의 시간 복잡도로 힙 성질을 유지

  • 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.
    
  • 이후 루트 노드에서부터 하향식으로 Heapify()를 진행한다.
    

👁️‍🗨️ 참조
유튜브 동빈나 (https://youtu.be/AjFlp951nz0)
https://www.geeksforgeeks.org/heap-data-structure/
https://medium.com/@aahana22012001/heap-and-heap-sort-algorithm-9bc53eb8672e