Priority Queue and Heap

강의 : https://www.edwith.org/datastructure-2019s2/joinLectures/22005

 

1.Queue

 

input gate와 output gate가 별개로 존재하는 data storage

 

Data In : Enqueue

Data out : Dequeue

 

Queue에 In 한 순서대로 데이터 Out. (FIFO) 

 

2. Priority Queue

Queue 에 들어가는 data에 우선순위(Priority)가 존재함!

들어온 순서에 상관 없이 우선순위가 높은 data 먼저 dequeue.

 

- Lazy approach == Unsorted implementation

            : Enqueue 할 때는 그냥 넣고 -> Dequeue 할 때 priority 순으로 out!

-Early-Bird approach == Sorted implementation

            : Enqueue 할 때부터 priority 순으로 sorting 하여 넣음 -> Dequeue할 때 그냥 out!

 

 

3. Priority Queue 의 Structure

Priority Queue는 array, linked list, heap 으로 구현할 수 있다.

 

Heap 이란?

Priority Queue를 위해 만들어진 자료구조. binary tree의 일종이다.

 

Balanced tree

트리 size = n , 높이 = h 일 때, 

2**h - 1 < n <= 2 ** (h+1) -1 을 만족하는 tree!

 

(1) 2 ** h -1 < n 이란?

상단은 full tree 이다!

       *full tree란? 완전한 삼각형 모형을 갖춘 tree 구조

(2) 2** (h+1) -1 이란?

maximum height 노드(leaf 노드들) 을 채워나가는 중이다.

 

*Tree 구조형 상관관계 정리

Balanced Tree ⊃ Complete Tree ⊃ Full Tree 

 

4. Binary Heap

ㅁBinary Heap의 조건

(1) Shape property : Complete Tree 형식을 갖춰야 한다!

(2) Heap property : 각각의 node 는 그의 children보다 크거나 같아야 한다. (max heap일 경우)

===> 따라서 Dequeue 할 때 root 만 보면 되므로 easy~ 하다.

 

따라서 Binary Heap을 만족한다면 데이터를 넣고 뺼 때 아주 간단해진다.

(1) tree size (n) 을 알면 다음 데이터가 어느 위치에 들어가야 하는지 구조적으로 계산할 수 있다.

n 이 11 이라고 가정할 때 ,

- 상단이 Full Tree 이므로, 2 ** h - 1 개의 데이터가 있음.

- Complete Tree이므로 maximum height 의 node를 채워나가는 중임. ( n - (2**h -1) 을 하면 n 번째 데이터가 어디에 위치할지 알 수 있음 -> 4번째 node ( computer 식으로 thinking 하면 0->1->2-> "3"번째 index node)

 

(2) Traversal 할 때에도 완전 빨리 찾을 수 있다!

- (1)에서 n 번째 데이터가 몇 번째 node에 들어가는지 index를 알 수 있다. "3"

- 3을 2진수로 바꿔준다. " 3(10) -> 11(2)"

- 갈림길 선택을 몇 번 하는가? h 번 해야 함. 따라서 h 자리 만큼 0 을 앞에 붙여준다. " 011 "

- 0은 왼쪽 길 1은 오른쪽 길을 의미한다. 

- root 에서부터 0(왼쪽) - 1(오른쪽) - 1(오른쪽) 을 따라 내려가면 n 을 찾을 수 있다! 

 

위 계산법으로 데이터를 array에 넣으면 빠르다!

-array index 계산법:

(1) root index : 0

(2) i 번째 노드의 parent : ( i - 1 ) / 2

(3) i 번째 노드의 left child: 2i + 1

(4) i 번째 노드의 right child: 2i +2

(5) 다음에 insert 할 노드 : tree size -1

 

ㅁ Binary Heap의 동작

Insert 할 때 : Percolate - up

 

(1) Data 는 일단 leaf 에 Insert 된다.

(2) binary heap의 조건( heap property ) 을 맞추기 위해 inserted data 는 점차 root 방향으로 올라간다.

(3) 재귀적으로 반복!

 

Delete  할 때 : Percolate - down

(1) Data 는 Root 에서 Dequeue 된다.

(2) binary heap의 조건( shape property ) 을 맞추기 위해 일단 Root 값을 last node로 대체한다.

(3) binary heap 의 조건 ( heap property ) 을 맞추기 위해 children 의 값들과 비교하며 leaf 방향으로 내려간다.

(4) 재귀적으로 반복!

Q. (2)(3) 번 과정이 너무... 비효율적이지 않나? 다른 방법이 없을까..?

 

Complexity of Priority Queue

Binary Heap을 사용하면, binary tree의 일종이기 때문에  Enqueue, Dequeue 모두 ... O( log N )  !!!