우선순위 큐

우선순위큐 개념 정의 우선순위큐는 들어온 데이터의 우선순위에 따라 데이터를 꺼내는 자료구조입니다. 큐는 들어온 순서에 따라 데이터를 꺼내는 반면에 우선순위큐는 우선순위에 따라 데이터를 꺼냅니다. 우선순위 큐는 3가지 방식으로 구현할 수 있습니다. ① 배열 ② 연결리스트 ③ 힙으로 구현할 수 있습니다. 배열과 연결리스트의 경우, 정렬의 유무에 따라 데이터 처리의 시간복잡도가 O(N) ~ O(NlogN)이나 힙의 경우 O(logN)으로 동일합니다. 따라서 우선순위큐는 힙으로 구현합니다. 힙 자료구조 구현 힙 자료구조는 완전이진트리의 한 형태로 리프노드를 제외한 모든 노드들이 점유되어 있고 자식노드는 왼쪽부터 채워지는 구조입니다. 완전이진트리의 특징은 다음과 같습니다. 1. 리프노드를 제외한 모든 레벨에 노드..