학습 일자 : 2023.04.24

Heap

부모 노드의 우선순위가 자식 노드보다 특정 규칙에서 우위를 차지하는 형태를 유지하는 완전 이진트리 형태의 자료구조

• 만약, 규칙이 우선순위가 오름차순이라면? 부모의 우선순위가 자식 노드의 우선순위보다 무조건 높아야 함.
• 우선순위가 내림차순이라면? 부모 노드의 우선순위가 자식 노드의 우선순위보다 무조건 낮아야 함

부모 노드는 최대 2개의 자식 노드를 가질 수 있음

메모리의 힙영역과는 전혀 상관이 없음. 단순히 이름만 같은 것.

우선순위 큐

우선순위를 입력 받아 우선순위가 높은 순서대로 반환하는 자료구조

보통 행동의 우선순위대로 실행해야 할 때 사용함.

ex.게임에서 플레이어 행동 우선순위 정의

✌HEAP✌을 이용한 어덥터 패턴으로 구현 한것 바로 PriorityQueue(우선순위 큐)임

PriorityQueue<string, int> priorityQ = new PriorityQueue<string, int>();

priorityQ.Enqueue("감자", 3);
priorityQ.Enqueue("당근11", 1);
priorityQ.Enqueue("당근22", 1);
priorityQ.Enqueue("토마토", 2);

while(priorityQ.Count > 0)
{
	Console.WriteLine(priorityQ.Dequeue()); //우선수위가 높은 순서대로 출력 됨.
}

| [output] 당근11 → 우선순위가 동일한 경우, 먼저 들어간 데이터가 먼저 출력 됨. (기본 구조가 큐이기 때문임) 당근22 토마토

[우선순위를 내림차순으로 정렬]

(HEAP은 기본적으로 오름차순으로 데이터가 나옴.)

PriorityQueue 선언 시점에 생성자에 Comparer 조건을 넣어주면 됨!

PriorityQueue<string, int> desc = new PriorityQueue<string, int>(Comparer<int>.Create((a, b) => (b -a))); 

| [output] 양파 마늘 감자 토마토 당근11

우선순위 큐 시간 복잡도