Priority queue

Priority queue

    - 큐에 우선순위가 적용된 추상적 개념

    - 우선순위가 높은 요소를 먼저 꺼내는 자료구조

 

 

특징

    - 일반적으로 힙의 구조

    - 힙 구조일 경우, 삽입과 삭제의 시간 복잡도 : O(logN)

    - 힙 구조를 알아보기

 

 

구현

    - 배열

        * 문제점 1 : 우선순위가 중간인 값을 삽입할 때, 삽입하는 위치 뒤에 있는 모든 요소를 옮겨야 함

        * 문제점 2 : 요소를 찾을 때, 우선순위를 비교해야 하므로 최악의 경우에는 모든 요소와 비교해야 함. 시간복잡도 O(n)

 

    - 연결 리스트

        * 문제점 1 : 요소를 찾을 때, 우선순위를 비교해야 하므로 최악의 경우에는 모든 요소와 비교해야 함. 시간복잡도 O(n)

 

    - 힙

        * 장점 1 : 이진 트리의 깊이가 증가할 때마다 저장 가능한 자료의 개수는 2개가 되고, 비교 연산 횟수는 1회 증가합니다. 그래서 트리의 깊이는 logN이 됩니다. 따라서, 연결 리스트로 구현하면 삽입과 삭제의 시간 복잡도는 O(logN)을 갖습니다.