[알고리즘] Heap & Priority Queue

🎈 Heap (힙)

• 완전 이진 트리 자료구조의 일종 (왼쪽에서 오른쪽으로 데이터가 차례대로 삽입되는 트리)
• 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 사용하는 알고리즘
• 항상 루트 노드(root node)를 제거한다.
• 최소 힙(min heap) : 루트 노드가 가장 작은 값을 가짐 ➡️ 값이 작은 데이터가 우선적으로 제거됨
• 최대 힙(max heap) : 루트 노드가 가장 큰 값을 가짐 ➡️ 값이 큰 데이터가 우선적으로 제거됨

🎈 Heap 구현

• 주로 배열로 구현됨
• 부모 노드와 자식 노드의 관계
  - 왼쪽 자식 노드의 인덱스 : 부모 노드 인덱스 2
  - 오른쪽 자식 노드의 인덱스 : 부모 노드 인덱스 2 + 1
  - 부모 노드의 인덱스 : 자식 노드 인덱스 / 2

🎈 Priority Queue (우선순위 큐)

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 데이터를 우선순위에 따라 처리하고 싶을 때 사용
• 구현 방법
  1. 단순히 리스트를 이용하여 구현
  2. heap(힙)을 이용하여 구현

⏳ Priority Queue 시간 복잡도

• N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 힙 정렬과 동일 ➡️ O(NlogN)

✏️ 자료구조 정리

• 스택(Stack) : 가장 나중에 삽입된 데이터
• 큐(Queue) : 가장 먼저 삽입된 데이터
• 우선순위 큐(Priority Queue) : 가장 우선순위가 높은 데이터