
[CS기초] 우선순위 큐(Priority Queue)
·
크래프톤 정글/CS기초(키워드, 개념정리)
우선순위 큐우선순위 큐(Priority Queue)는 pop 연산에서 가장 먼저 들어온 원소 대신 우선순위가 가장 높은 원소가 내보내지는 큐이다. 이는 일반적으로 힙(Heap)을 이용하여 구현됩니다. 힙(Heap)우선순위 큐를 효율적으로 구현하기 위해 사용되는 특수한 이진 트리 형태의 자료구조. 힙은 다음 두 가지 조건 중 하나를 만족해야 한다.최소 힙(Min-Heap) : 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같아야 한다. 즉, 루트 노드가 트리 전체에서 가장 작아야 한다. 최대 힙(Max-Heap) : 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같아야 한다. 즉, 루트 노드가 트리 전체에서 가장 커야 한다. 힙의 특징완전 이진 트리 구조 : 트리의 모든 계층이 꽉 차 있고, 마지막..