[CS 노트] : Queue와 Priority Queue 비교

Queue와 Priority Queue를 비교하라

 

큐는 먼저 들어간 데이터가 먼저 나오는 형식이고 우선순위 큐는 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오게 된다. 때문에 큐의 push, pop의 시간 복잡도는 O(1)이지만 우선순위 큐의 push, pop의 시간 복잡도는 O(logn)이 된다.

 

우선순위 큐와 힙

우선순위 큐는 Heap과 같다고 볼 수 있다. 힙은 완전이진트리 구조이다. 이 힙은 Max Heap과 Min Heap이 있다.

 

Max Heap은 각 노드에 저장된 값이 자식 노드의 값 보다 크거나 같아야 하고 Min Heap은 반대로 각 노드의 저장된 값이 자식 노드의 값보다 작거나 같아야한다.

 

힙은 트리 구조로 이루어져 있고 트리는 보통 Linked List로 구현하지만 힙은 array로 구현한다. 왜냐하면 새로운 데이터를 마지막에 추가해야 하는데 이 과정이 array가 편하기 때문이다.

 

Max Heap Push, POP의 경우 어떻게 되나?

 

새로운 데이터가 들어오면 마지막 인덱스에 값을 저장하고 부모 노드와 값을 비교한다. 새로 들어온 데이터가 부모 노드보다 값이 크다면 부모 노드와 스왑을 해준다. 이 과정이 부모 노드의 값이 더 클 때 까지 반복하면 되고 이렇게 되면 시간 복잡도는 O(n)이 된다.

 

반대로 데이터가 나간다면 가장 큰 값이 나가게 되고(Root Node) 일단 그 빈 공간을 맨 마지막에 있는 인덱스로 넣어주고 Max Heap의 조건으로 자식 노드와 값을 비교한다. 그러면서 점점 정리해 나가면 된다. 이렇게 되면 POP의 경우 시간 복잡도는 O(n)이 된다.

---

기출로 대비하는 개발자 전공면접 [CS 완전정복] 을 참고해서 공부하였습니다.