[CS / Array vs Linked List] ep09. Queue vs priority queue를 비교하여 설명해 주세요

🤔 면접 질문

 

Q1. Queue vs priority queue를 비교하여 설명해 주세요

 

A1.  Queue 자료구조는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 구조로 저장하는 형식입니다. 이와 다르게 우선 순위 큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옵니다.

 

Queue의 operation의 시간복잡도는 enqueue = O(1), dequeue = O(1)이고, Priority queue는 push = O(logn), pop = O(logn)입니다.

 

 

 

💡 면접🐕🍯 tip

 

: 면접질문에서 '우선 순위 큐'를 잘 답하기 위해서는 구현 방법과 operation의 시간 복잡도를 잘 설명할 수 있어야 한다. 우선 순위 큐를 구현하라고 하면 Heap을 구현하면 된다. Heap 자료구조는 이진 완전 트리를 활용하는 것이고, 대표적인 operation의 시간 복잡도는 'push = O(logn) , pop = O(logn)' 이다. 이 두 가지 특징을 중심으로 공부해 가면 충분히 답변할 수 있다. 또한 tree가 그려져 있는 상태에서 최대 힙, 최소 힙의 삽입과 삭제 시에 어떻게 node가 삭제되고 연결이 변경되는지의 과정을 그려서 설명할 수 있다면 더 좋다.

 

 

 

1️⃣ Heap

 

Heap은 그 자체로 '우선 순위 큐(Priorty Queue)'의 구현과 일치한다. Heap은 '완전 이진 트리 구조'로써, Heap이 되기 위한 조건은 다음과 같다.

 

• 각 noe에 저장된 값은 child node들에 저장된 값보다 작거나 같다.(=min heap)

 

 

 

 

 

2️⃣ Heap 구현

 

트리는 보통 Linked list로 구현해야 한다. 하지만 Heap은 tree임에도 불구하고 array를 기반으로 구현해야 한다. 그 이유는 새로운 node를 힙의 '마지막 위치'에 추가해야 하는데, 이 때 array 기반으로 구현해야 이 과정이 수월해지기 때문이다.

 

• 구현의 편의를 위해 array의 0번 째 index는 사용하지 않는다.
• 완전 이진 트리의 특성을 활용하여 array의  index만으로 부모 자식 간의 관계를 정의한다.
  • n번 째 node의 left child node = 2n
  • n번 째 node의 right child node = 2n + 1
  • n번 째 node의 parent child node = n / 2

 

 

 

 

3️⃣ Heap push - O(logn)

 

heap tree의 높이는 logN이다. push()를 했을 때, swap하는 과정이 최대 logN번 반복되기 때문에 시간 복잡도는 O(logn)이다.

 

 

 

4️⃣ Heap pop - O(logn)

 

push()을 했을 때, swap하는 과정이 최대 logN번 반복되기 때문에 시간 복잡도는 O(logN)이다.

 

• 각 node에 저장된 값은 child node들에 저장된 값보다 더 크거나 같다. ( = Max Heap)

  👉 root node에 저장된 값이 가장 큰 값이 된다.