프로그래밍/기본기ㆍ자료구조
2020. 4. 14.
Priority Queue (우선순위 큐)
개념 - 큐의 스케줄링 방법 중 하나 - 각 원소들이 우선순위를 가지고 높은 우선순위를 가진 원소가 낮은 우선순위를 가진 원소보다 먼저 처리 - 원소가 같은 우선순위를 가지고 있다면 큐에 의해 먼저 삽입된 순서대로 처리되는 자료구조 - 배열, 리스트, 힙트리를 이용해서 구현할 수 있음 *배열, 리스트, 힙트리로 구현 시 - 배열로 구현할 경우 데이터 삽입 및 삭제 과정에서 비효율적 - 리스트로 구현할 경우 첫번째 노드와 마지막 노드까지 저장된 데이터와 우선순위 비교를 해야함 - 배열과 리스트는 정렬을 위해 요소 하나를 추가할 떄마다 이분검색 등을 이용해서 삽입될 위치를 찾아야함 - 힙트리의 구조를 이용하면 효과적으로 구현할 수 있음 (힙트리는 최소,최대값 기준으로 정렬되고 모든 내부 노드는 자신의 부..
