바이너리 힙 정의의 힙 속성이 재귀 적으로 적용됩니까?

문제

binary heaps의 정의는 완전한 바이너리 트리 여야하며 힙 속성에 따라 힙 속성을 따라야합니다. 각 노드에 저장된 키는노드의 아이들의 키.

위의 트리에서, 값 (70)이있는 노드는 힙 속성을 파괴하는 부모 (10)보다 크다.그러나 70은 40보다 크고 40의 하위 트리에 놓여 있습니다. 40 명이 두 자녀가 10과 2보다 큽니다.

간단한 용어로 루트의 하위 트리의 모든 노드가 루트보다 작아야합니까?

해결책

나는 대부분의 사람들이 "재귀"힙 속성을 어디서나 유지하기에 충분한 정의가 있기 때문에 힙 속성이 정점 및 즉각적인 자식에만 적용된다고 생각할 것입니다.그것은 그것에 대해 생각하는 클리너 방법입니다 (꼭지점 당 힙이 힙이되는지 확인하십시오).

나는 이것에 정확히 합의가 있는지 모르며, 아마도 다른 사람들은 다르게 생각한다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 cs.stackexchange