기말준비-우선순위 큐 (Priority Queue)

Heap : 완전 이진트리, 배열 H[1...N]에 저장됨.

Heap의 성질 : P >= L,R (Max heap)  or  P <= L,R (Min heap)

 

1. Heap에 삽입

 - Heap의 제일 끝에 Data를 추가 한 뒤, 그 Data를 data의 parent와 비교해서 위로 올릴지 내릴지 결정을 반복.

 - MaxHeap을 만드는 과정이므로, 부모보다 큰 자식이 있으면 안됨.

 

2. Heap에서 삭제

 - 최댓값인 Root (H[0])을 삭제 후 맨 마지막 원소를 Root로 이동, 그리고 그 이동된 원소를 parent와 비교하며 내림.

 - MaxHeap이 되야하므로, 자식보다 작은 부모가 있으면 안됨.

 

3. 초기 힙 구성 : 배열 H[1...N]에 N개의 data가 입력되어짐.

 3-1) Top-down(하향식) 구성

  - H[1]을 입력한 size 1의 Heap을 초기 생성 후, 2~N까지 차례로 추가함 (HeapAdd를 N번 반복)

   => Heap이 위에서 아래로 확장    // O(N lgN)

 

 3-2) Bottom-up(상향식) 구성

 - 모든 단말 노드를 Heap으로 구성한 후, N/2 ~ 1 까지 차례대로 추가함 (HeapDown을 N/2번 반복)

  => Heap이 아래에서 위로 확장    // O(N)

 

 3-3) 상향식이 하향식보다 빠른 이유

 

 하향식 : 1*0 + 2*1 + 2^2*2... 이렇게 변수가 같이 올라감

 상향식 : 1*h + 2*(h-1) + 2^2*(h-2)... 이렇게 한쪽은 올라가고 한쪽은 내려감.