27. 우선순위큐(Heap/Prirority Queue) 알고리즘

1. 개요

 우선순위 큐는 쉬움.

 Max Heap이란 부모가 자식보다 값이 더 큰 우선순위 큐.

 Min Heap이란 부모가 자식보다 값이 더 작은 우선순위 큐.

 우선순위 큐는 완전이진트리임. 그러므로 부모와 자식 인덱스를 쉽고 빠르게 찾기 위해 자료구조 배열 사용하는 것이 좋음.

 Index X의 자식은 Left: (X*2)+1, Right: (X*2)+2.

 Index X의 부모는 (X-1)/2. 예를들어, (7-1)/2 == (8-1)/2 == 3. 인덱스 7과 8의 부모는 3으로 같다.

 

 Heap의 규칙

 (1) 모든 삽입은 맨 마지막 자리에 들어감. 

     그 뒤, Heap 거슬러 오르며 부모와 값을 비교하여 Max/Min Heap 규칙에 맞게 자리를 찾아감.

 (2) 모든 삭제는 가장 최상위 노드(즉, Index 0)에서 빠져나옴.

     그 뒤, 맨 마지막 노드 값을 최상의 노드 값으로 채움. 그 후, 아래로 내려가며 Max/Min Heap 규칙에 맞게 자리 찾음.

2. 문제

 우선순위 큐 (Heap)을 설계하시오. 생성, 삽입, 삭제 기능을 추가하시오.

 (메모리 꽉 차면, 자동으로 데이터 크기 조절 함수도 만드시오.)

3. 출력

3-1) 함수 및 구조체 선언

3-2) 메인

3-3) 부모 및 자식 인덱스 추출 함수

3-4) 힙 생성

3-5) 크기 조절

3-6) 삽입 

3-7) 삭제

3-8) 출력(Min/Max)

4. 정리

 기억해야 할 것.

 (1) 힙의 삽입은 언제나 맨 끝에서 이뤄진다.

 (2) 힙의 삭제는 언제나 맨 앞에서 이뤄진다.

 (3) 완전이진트리 내부에서 조정되기 때문에 하나의 삽입과 삭제는 O(logn)의 시간이 소요.

 (4) 부모와 자식의 값의 비교로만 움직인다.