SplHeap 클래스의 top 메서드는 max heap의 특성을 이용하여 heap의 루트 노드(최대값)를 반환합니다.
max heap의 특성은 부모 노드의 값이 자식 노드의 값보다 항상 큰 것입니다. 따라서, 루트 노드(최대값)는 항상 heap의 최대값입니다.
top 메서드는 다음과 같은 과정을 거칩니다.
1. 루트 노드(최대값)를 반환합니다.
2. 루트 노드의 자식 노드들을 확인합니다.
3. 루트 노드의 자식 노드 중 최대값이 루트 노드보다 큰 경우, 루트 노드와 자식 노드의 최대값을 교환합니다.
4. 루트 노드의 자식 노드 중 최대값이 루트 노드보다 큰 경우, 루트 노드와 자식 노드의 최대값을 교환합니다.
5. 루트 노드의 자식 노드 중 최대값이 루트 노드보다 큰 경우, 루트 노드와 자식 노드의 최대값을 교환합니다.
이 과정을 반복하여 루트 노드의 자식 노드 중 최대값이 루트 노드보다 큰 경우까지 반복합니다.
예를 들어, 다음과 같은 max heap이 있다고 가정해 보겠습니다.
#hostingforum.kr
10
/
8 9
/ /
7 6 5 4
top 메서드를 호출하면 루트 노드(최대값)인 10이 반환됩니다.
이후 루트 노드의 자식 노드 중 최대값인 9를 확인하고, 루트 노드와 자식 노드의 최대값을 교환합니다.
#hostingforum.kr
9
/
8 10
/ /
7 6 5 4
이러한 과정을 반복하여 루트 노드의 자식 노드 중 최대값이 루트 노드보다 큰 경우까지 반복하면, 최종적으로 다음과 같은 max heap이 됩니다.
#hostingforum.kr
10
/
9 8
/ /
7 6 5 4
top 메서드는 이러한 과정을 거쳐 heap의 루트 노드(최대값)를 반환합니다.
2025-05-22 11:10