c++) Priority Queue 구현

https://yoongrammer.tistory.com/80

[자료구조] 힙 (Heap) or 이진 힙(binary heap)

(위 yoongrammer님의 블로그를 보고 공부했습니다) 

 

 

- 우선순위 큐는 주로 Heap 구조로 구현된다.

 

- Heap 구조는 최댓갓 최솟값을 빠르게 찾기위해 고안된 완전 이진 트리를 기본으로한 자료구조다.

 

- 구현할때는 배열을 이용해 구현하며, 편의를 위해 시작 인덱스는 0이 아닌 1부터 시작된다. 

 

- 노드들의 인덱스는 다음과 같은 특성들을 갖고 있다.

• 노드 i의 부모 노드의 인덱스 = floor(i / 2) 
• 노드 i의 왼쪽 자식의 인덱스 = i * 2
• 노드 i의 오른쪽 자식의 인덱스 = i * 2 + 1 

 

- 기억해야 할 점은 heap 에서는 부모가 자식보다 큰 우선순위를 갖는 것은 보장되지만, 형제들끼리는 보장되지 않는다.

  즉 heap 구조로 저장된 배열을 쭉 출력해봤을때 정렬되있는 상태는 아니라는 것이다.

 

 

 

---

위와 같이 100, 20, 200을 큐에 넣고 배열을 출력해보면 200, 100, 10이 아닌 200, 10, 100이 출력되는 것을 알 수 있다.

이는 heap은 부모가 자식보다 큰 값을 갖는것은 보장되지만, 형제들끼리는 그렇지 않기 때문이다.

200이 루트, 10, 100은 루트의 왼쪽자식과 오른쪽 자식이다. 

 

---

두개의 변수를 갖는 Node 구조체의 첫번째 변수 기준으로 내림차순한 우선순위 큐