알고리즘 4 우선순위 큐와 힙

우선순위 큐 ; 큐의 각 요소가 우선순위를 갖는 큐 

-> 삽입 시, 우선순위에 맞게 큐가 다시 정렬된다

-> 제거 시, 가장 앞의 노드가 제거된다

 

힙 ; 

* 여기서 힙은 힙 순서 속성을 만족하는 이진 트리를 말하는 것으로, 

프로그래밍 언어에서 말하는 자유저장소 힙이 아니다 

힙순서속성; 트리 내의 모든 노드가 부모 노드보다 큰 완전 이진트리   

* 힙은 단순히 힙순서속성만 만족하므로 이진트리+이진트리탐색을지원하지않는다 

* 힙의 존재가치는 루트 노드가 항상 최솟값 노드라는 점! 

 

힙의 두 가지 연산

1. 새 노드 삽입

- 완전이진트리를 만족하는 가장 낮은 곳으로 새 노드 삽입 판단 

- 부모노드와 비교 

- 부모보다 우선순위 높을 경우, 부모와 교환 -> 반복 

2. 최솟값 삭제  

- 최솟값 삭제 = 루트 노드 삭제 

- 힙의 최고 깊이, 가장 우측 노드를 루트로 올림 

- 올라온 노드와 자식 노드 비교 -> 가장 작은 값과 자리 교환 -> 반복  

 

힙 구현 

- 링크드 리스트로 할 경우, 최솟값 삭제를 구현할 때, 최고 깊이 가장 우측 노드 탐색이 불편함

- 따라서, 배열로 구현한다 ! 

 

- 깊이 n의 노드는 2^n개의 노드를 갖고 2^n-1 부터 2^(n+1)-2의 인덱스를 갖는다 

- k번 인덱스 노드의 차일드는 2k+1 2k+2다. 

- k번 인덱스 노드의 부모는 (k-1)/2의 몫이다. 

 

 

GitHub - Sukmin-LanternK/Heap