728x90 반응형 Min Heap1 자료구조 - 우선 순위 큐(Priority Queue) 1. 우선순위 큐란? 우선순위 큐(Priority Queue)는 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리되는 자료구조이다. 큐는 선형 자료구조이고, 우선순위 큐는 비 선형 자료구조이다. 우선순위 큐는 자료가 들어온 순서와 상관 없이 미리 정한 우선순위대로 나간다. 주로 정의된 우선 순위를 heap condition으로 가지는 heap을 이용해 구현된다. 그 이유는 시간 복잡도와 관련이 있는데, 배열 기반 데이터 삽입의 시간 복잡도는 O(n) 이고 배열 기반 데이터 삭제의 시간 복잡도는 O(1)이다. 또 연결 리스트 기반 데이터 삽입과 삭제의 시간 복잡도도 위와 같다. 하지만 힙 기반 데이터 삽입과 삭제의 시간 복잡도는 각각 O(logn)이다. 따라서 힙을 먼저 공부해야 한다... 2021. 1. 7. 이전 1 다음 728x90 반응형