개념 - 우선순위 큐와 힙

일반적인 큐는 먼저 들어온 순서대로 나가지만

우선순위 큐는 말그대로 정해진 우선순위에 따라 먼저 나가는 자료구조를 말한다.

운영체제에서 시스템 프로세스의 우선처리, 네트워크 패킷에서 관리 패킷의 우선처리 등에 사용된다.

스택, 큐와 마찬가지로 배열, 연결리스트로도 구현할 수 있으나 힙이 가장 효율적인 구조라고 한다. 

최대 우선순위 큐 : 우선순위가 높은 순서대로 삭제

최소 우선순위 큐 : 우선순위가 낮은 순서대로 삭제.

ADT

insert(item) : 항목 추가

remove() 우선순위가 높은 요소 삭제, 반환

find() 우선순위가 높은 요소 반환

isEmpty() 공백인지 검사

isFull() 포화상태인지 검사

display() 모든 요소 출력

구현방식에 따른 시간 복잡도

정렬되지 않은 배열

삽입할 때는 뒤에 추가하면 되므로 O(1), 삭제할 때는 매번 전체의 우선순위를 조회해야하므로 O(n). 

삭제할 때 뒤의 원소들을 땅겨야 한다.

정렬된 배열

삽입할 때 우선 삽입할 위치를 찾아야 한다. 

순차라면 O(1), 이진탐색을 하면 O(log2 n)이 필요하지만, 삽입할 때 뒤로 한칸씩 밀어야 하므로 O(n)

정렬되지 않은 연결리스트

위와 마찬가지로 삽입할 때는 O(1), 삭제할 때는 O(n)

정렬된 연결리스트

삽입할 때 O(n), 삭제할 때 O(1)

힙 : 완전히 정렬된 것은 아니지만, 전혀 정렬되지 않은 것도 아닌 상태 

삽입 : O(log n), 삭제 : O(log n)

힙

우선순위 큐를 위해 만들어진 이진트리 자료구조로, 여러 값들 중에서 가장 큰값, 가장 작은 값을 빠르게 찾아내도록 만들어졌다.

이진탐색 트리와 달리 중복된 값을 허용하며, 완전 이진트리여야 한다.

최대 힙 ( max heap ) : 부모 노드의 키 값이 항상 자식 노드의 키 값보다 크거나 같다.

최소 힙 ( min heap ) : 부모 노드의 키 값이 항상 자식 노드의 키 값보다 작거나 같다. 이 둘은 부등호만 다르다.

힙의 구현

이진트리이므로 차례대로 번호를 매길 수 있고, 완전 이진트리라 빈 요소가 없기 때문에

노드의 번호를 배열의 인덱스라 생각하고 배열로 효과적으로 표현할 수 있다.

배열로 완전이진트리를 표현할 경우 자식노드와 부모노드의 관계를 인덱스로 쉽게 계산할 수 있다.

이 때 0번째 원소는 비워둔다.

힙의 연산

삽입시에는 우선 맨 뒤에 놓는다. 그리고 부모와 비교해가며 루트에 도달하거나 더 큰 값을 만날 때까지 이동한다.

삭제시에는 우선 맨 앞에 놓는다. 그리고 자식과 배교해가며 더 작은 값을 만날 때까지 이동한다.자식들 중에 큰 값과 교환이 일어난다.

추가

std의 priority_queue

큐, 스택과 마찬가지로 컨테이너 어댑터의 역할을 한다. 기본은 벡터를 사용하고 top()을 호출하면 back을 반환해준다. 

하나씩 삽입하면 O(nlogn) 이지만 한번에 구성하면 O(n)이다.  하나씩 전부 삭제할 때도 O(nlogn)