Priority Queue 란?

일단 이전에 배웠던 '큐Queue'는 스택과 반대로 '먼저 들어온것이 먼저 나가는' FIFO 방식의 자료구조다. 특징으로는 스택과 달리 들어가는 방향과 나오는 방향이 달라서 조금은 구현하기 까다로웠다는 점.

우선순위큐에서는 들어온 순서랑 상관 없이 어떤 기준으로 우선순위를 결정해 그 우선순위대로 나가는 큐다.

적용 사례들 :

• 데이터 압축 : 허프만 알고리즘
• 최단 거리 : 다이크스트라 알고리즘
• 최소 신장 트리 : 프림 알고리즘

구현 방법

기본적인 구현

정렬되지 않은 배열로 구현 정렬되지 않은 (링크드)리스트로 구현 정렬된 배열로 구현 정렬된 (링크드)리스트로 구현

정렬되지 않은것과 정렬된것의 차이는 자료를 삽입할 때 많은 일을 할것이냐, 꺼낼 때 많은 일을 할것이냐의 차이다. 정렬되지 않고 구현하려면 삽입은 그냥 맨 마지막 index에 추가하고, 꺼낼 때 (우선순위 기준이 '가장 작은 값'이라면) 그때마다 가장 작은 노드를 찾고 그 노드를 가져오는것. (삽입시에 $O(1)$, 꺼낼시에 $O(n)$의 복잡도) 정렬시켜 구현하려면 삽입을 할 때마다 자신보다 큰 것의 index를 찾아 그 자리에 넣고 나머지 뒤의 노드들을 한 i칸씩 이동시키고, 꺼낼때는 즉시 바로 맨 앞의 노드를 꺼내면 된다. (반대로 삽입시에 $O(n)$, 꺼낼시에 $O(1)$의 복잡도)

이진 트리 구현

이진 검색 트리 구현 : 삽입과 삭제 모두 평균 $O(logn)$의 복잡도. 최악의 경우(극단적으로 경사져서 리스트와 거의 다를바 없는 트리) $O(n)$.

균형 이진 검색 트리 구현 : 삽입과 삭제 모두 최악의 경우 $O(logn)$

위에서 본 배열,리스트 구현에서 정렬 여부에 따라 삽입과 삭제가 각각 현저히 다른 복잡도를 가진다. 그래서 용도별로 삽입이 많으면 비정렬 방식으로 구현하고, 삭제가 많으면 정렬 방식으로 구현하면 된다. 그런데 삽입과 삭제 모두 일정한 복잡도를 가지길 원한다면 이진 검색 트리로 구현하면 된다.

이진 힙 구현

'힙Heap'이라는 아직 배운적 없는 자료 구조로도 구현할 수 있다. 바로 다음 수업에서 다룬다고.