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

Queue

큐는 FIFO구조로 먼저 들어온 데이터가 먼저 나가는 구조이다.

 

Priority Queue

들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나온다. 예를 들어 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건보다 꺼내서 확인해야 하는 경우이다.

우선순위큐를 구현하는 방법

01 리스트를 이용

데이터의 개수가 N개 일 때, 구현 방식에 따라서 시간 복잡도 삽입시간 O(1), 삭제 시간 O(N)

02 힙(Heap)을 이용

데이터의 개수가 N개 일 때, 구현 방식에 따라서 시간 복잡도 삽입시간 O(logN) (힙의 조건을 유지하기 위해 부모 노드와 비교하면서 올라간다) ,삭제 시간 O(logN)(루트 노드를 삭제한 후 힙을 재조정해야 한다)  

---

Heap

완전 이진 트리 자료 구조의 일종이다. 항상 루트 노드를 제거한다.

01 최소 힙(Min Heap)

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

02 최대 힙(Max Heap)

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

완전 이진 트리

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

---

Heap 동작 예시

01 새로운 원소가 삽입될때

Min-Heap에서 원소를 추가할 때

https://smellycode.com/binary-heap/

---

 

02 원소가 삭제될때

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

https://in.pinterest.com/pin/max-heap-deletion-animated-example--547750373425240189/