우선순위 큐_대칭 최소최대 힙(Symmetric min max heap)

우선순위 큐_대칭 최소최대 힙(Symmetric min max heap)

Symmetric min max heap 은 root가 비어있고 루트 lch에는 가장 작은 값이 루트 rch에는 가장 큰 값이 있어서

우선순위의 최소 최대를 편하게 접근할 수 있는 완전 이진 트리(CBT)이다.

조건은 크게 3가지이다.

1. 각 노드의 원소는 오른쪽 형제보다 작거나 같다.

2. 조부모를 가진 노드 N -> 조부모의 rch > N

3. 조부모를 가진 노드 N -> 조부모의 lch < N 

이러한 조건을 만족시키는 대칭 최소최대 힙을 삽입하는 과정은 다음과 같다.

* 먼저 해당 위치에 E라는 임의 노드를 삽입.

그리고 조건 1을 체크를 한다(왼쪽 형제로 가서 값 비교, 오른쪽 형제로 가서 값 비교)

* 그리고 부모의 손자노드들로 가서 조건 2와 3을 하나씩 전부 체크.

구현 코드