우선순위 큐.md

우선순위 큐(Priority Queue)

• 우선순위 큐는 우선순위에 따라서 데이터를 추출하는 자료구조이다.
• 컴퓨터 운영체제, 온라인 게임 매칭 등에서 활용된다.
• 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현한다.

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

• 우선순위 큐는 다양한 방법으로 구현가능함.
• 데이터의 개수가 N개 일때 구현 방식에 따른 시간 복잡도

• 일반적인 큐는 선형적인 구조를 가진다.
• 반면에 우선순위 큐는 이진 트리 구조를 사용한다.

이진 트리

• 이진 트리는 최대 2개까지의 자식을 가진다.

포화 이진 트리(full binary tree)

• 왼쪽 포화 이진 트리는 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리이다.
• 오른쪽은 단순한 트리임

완전 이진 트리(complete binary tree)

• 완전 이진 트리: 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리이다.

높이 균형 트리(Hight Balanced Tree)

• 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이 나지 않는 트리이다.

참고

• 패캠 자료구조 나동빈