Suzzang's DevLab Suzzang's DevLab

우선순위 큐는 리스트와 완전 이진 트리를 활용하여 구현하는 두 가지 방법이 있다.예를 들어, 가장 작은 값을 먼저 빼내야 하는 경우를 생각해보면, 다음과 같은 시간 복잡도가 발생한다.리스트를 이용하는 경우정렬되지 않은 리스트에서는 삽입이 O(1)이지만 최소값을 찾는 데 O(N)의 시간 복잡도가 발생한다.정렬된 리스트를 사용할 경우, 삽입에 O(NlogN)의 시간이 걸리지만 최소값을 찾는 작업은 O(1)로 수행된다.완전 이진 트리를 이용하는 경우삽입과 삭제 모두 O(logN)의 시간 복잡도를 가지므로 더 효율적인 방법이다. 완전 이진 트리를 활용하려면 어떻게 구현해야 할까?완전 이진 트리를 효과적으로 구현하려면 힙(Heap) 자료구조를 사용하는 것이 적합하다.힙은 완전 이진 트리의 성질을 가지며 우선순위 ..