[DataStructure] Queue vs Priority Queue

Queue 와 Priority Queue 의 특징에 대해 정리하고자 한다. 

그리고 이와 관련된 Heap 구현에 대한 개념까지 같이 서술한다.

 

1. Queue

- 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO (First In First Out) 구조로 저장하는 형식
- 시간 복잡도는 enqueue 시 O(1), dequeue 시 역시 O(1)

 

2. Priority Queue

- 들어간 순서에 상관 없이 우선 순위가 높은 데이터가 먼저 나옴

- 시간 복잡도는 push 시 O(logn), pop 시 O(logn)

- Heap 자료구조를 바탕으로 한 구현 방식 

  - Heap 은 완전 이진 트리 구조이며, 조건은 다음의 경우가 있다.

    - 1) 각 Node 에 저장된 값은 Child Node 들에 저장된 값보다 크거나 같다 (Max Heap),

           따라서 Root Node 에 저장된 값이 가장 큰 값이 된다

    - 2) 각 Node 에 저장된 값은 Child Node 들에 저장된 값보다 작거나 같다 (Min Heap),

           따라서 Root Node 에 저장된 값이 가장 작은 값이 된다

  - Heap 구현

    - 보통 Tree 는 LinkedList 로 구현하지만, Heap 의 경우에는 똑같이 Tree 임에도 불구하고 Array 로 구현

      - 그 이유는 새로운 Node 를 Heap 의 ‘마지막 위치’에 추가해야 하는데, 이 때 Array 기반으로 구현해야 이 과정이 수월해짐

        - 구현의 편의를 위해 Array 의 0번째 Index 를 사용하지 않는다고 하고,

        - 완전 이진 트리의 특성을 활용해 Array 의 Index 만으로 부모 자식간의 관계를 정의한다.

          - N번째 Node 의 Left Child Node = 2n

          - N번째 Node 의 Right Child Node = 2n+1

          - N번째 Node 의 Parent Node = n/2

 

3. 출처

- https://www.inflearn.com/course/%EA%B0%9C%EB%B0%9C%EC%9E%90-%EC%A0%84%EA%B3%B5%EB%A9%B4%EC%A0%91-cs-%EC%99%84%EC%A0%84%EC%A0%95%EB%B3%B5