Top down Approach

                                                                                                                                                         

                                                                                                                                                                                                                   

                                                                                                                                                         

                                                                                                                                                                                                             

                                                                                                                                                                                                          

 

하향식(Top-Down) 방식은 노드가 

✔ ↓ 의 방향으로 먼저 간 다음, 

✔ → 의 방향으로 채워진다. 
이 두 순서로 노드가 채워지게 된다. 즉 위에서부터 채워나가되, 각 레벨에서의 삽입은 왼쪽에서 오른쪽 순서로 하게 된다.

이러기 위해선 두 가지 조건이 필요하다.
1. 각 노드에 저장된 값이 두 자식 노드에 저장된 값보다 크거나 같아야 한다. 작거나 같다는 조건으로 바꿔도 된다. 크기가 자식 노드보다 크거나 같은 경우를 Max heap이라 하고, 작거나 같은 경우를 Min heap이라고 한다.
2. 트리는 완전 균형 상태여야 하고, 마지막 레벨에 있는 leaf 노드들은 모두 트리의 가장 왼쪽 부분부터 채워져야 한다. 따라서 트리의 높이는 O(log n)이 된다.
이 두 조건은 자료구조 '힙'의 성질이기도 하다.

그렇다고해서 힙 구조에 저장된 데이터들이 완벽하게 정렬되어 있는 것은 아니다. 위의 두 가지 힙의 성질에 의거하여, 상하로는 크기의 규칙이 있으나 좌우로는 삽입 순서만 있지 크기의 순서에 대한 규칙은 없다. 즉 같은 레벨에 있는 노드들(이웃 노드)에 저장된 '값' 사이에는 아무런 순서 규칙이 없다.