[CS] 큐와 우선순위 큐를 설명해보세요

 

Queue 자료구조는 시간 순서로 먼저 넣은 데이터가 먼저 나오는  FIFO 저장방식이다.

enqueue O(1) / dequeue O(1)

 

 

Priority queue는 순서 상관없이 우선순위가 높은 데이터가 먼저 나온다. 

Heap은 우선순위큐의 구현과 일치하며 완전이진트리다.

트리는 대개 Linked list다. 그런데 Heap은 트리지만 array 기반이다. 이유는 새 node는 힙의 마지막 위치에 추가해야 하는데 그 과정이 array 기반이 편하기 때문이다. 

 

Heap 구현

 

array의 0번째 index는 편의를 위해 사용하지 않는다, 완전이진트리의 특성을 활용하여 array의 index만으로 부모 자식간의 관계를 정의한다.

n번째 node에서    left choild node = 2n  /  right child node = 2n+1  /  parent node = n/2

push O(logn) / pop O(logn)

 

max heap : 모든 node에 저장된 값은 child node들에 저장된 값보다 크거나 같아 root node가 가장 큰값.

새 데이터를 push하면 heap의 마지막 인덱스에 값을 저장한다. 부모 Node의 값이 더 작다면 swap를 하여 바꿔준다.

pop은 첫번째 인덱스에서 한다. 그러면 top의 빈공간이 생기는데 마지막 인덱스에 있는 값을 top으로 옮겨서 채운다. 그리고 top의 값이 child node보다 작다면 다음 레벨의 child node중 큰 값과 swap 한다. 이 swap을 child node가 더 크지 않을 때 까지 반복한다.

 

min heap : 모든 node에 저장된 값은 child node들에 저장된 값보다 작거나 같아 root node가 가장 작은값.

 

 

트리에서 최대·최소힙 삽입,삭제시 node의 삭제 및 연결과정을 설명해보자.