Study/Data Structure
-
우선순위 큐(Priority Queue)Study/Data Structure 2019. 12. 3. 12:24
우선순위 큐(Priority Queue) 응급실을 예로들면 응급한 환자부터 치료를 받듯이, 우선순위 큐는우선순위가 높은 데이터를 먼저 처리하는 자료구조이다. 우선순위 큐를 구현하는 세가지 방법 DS 삽입 삭제 배열 O(1) O(n) 연결 리스트 O(1) O(n) 힙(heap) O(log n) O(log n) 배열로 구현한 경우의 단점은 데이터 추가/삭제 과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 해야하기 때문에 시간이 오래걸린다. 또한 삽입 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야한다. 연결리스트의 경우에는 배열의 첫번째 문제는 해결이 되지만 삽입 위치를 찾기 위해 모든 노드의 데이터와 우선순위를 비교해야한다. 따라서 우선순위 큐를 위해 만들어진 자료구조라고 하는 힙..