최소 힙의 최대 항목이 리프 중 하나에 있음을 증명하는 것

최소 힙의 최대 항목이 N 항목이있는 트리의 리프 중 하나에 있어야한다는 것을 증명하려면 어떻게해야합니까?최소 힙의 최대 항목이 리프 중 하나에 있음을 증명하는 것

최소 힙의 전체적인 디자인을 이해하고 있으며 최대 항목이 리프 중 하나에 있음을 보여줄 수 있습니다 (깊이 N의 노드 N = 깊이 N의 노드). 증거를 형식화하는 방법에 대해 확신 할 수 없습니다.

가장 쉬운 방법은 대개 다음과 같습니다. 나는. 최대 항목이 리프에 없다고 가정합니다. 이것은 모순으로 이어질까요? –

또한 단순화를 위해 가장 큰 고유 항목이 있다고 가정하는 약간 더 쉬운 문제부터 시작하십시오. –

첫 번째 단계는 영어 설명이 여러 가지 다른 방식으로 해석 될 수 있기 때문에 귀하가 증명하고자하는 바를 정확하게 공식화하는 것입니다. 그 중 일부는 사실 (입증 할 수있는) 방법과 일부는 거짓 (증명할 수없는 방법)으로 해석 될 수 있습니다. –

"힙"속성은 리프가 아닌 노드를 루트로하는 하위 트리도 힙이기 때문에 힙 속성도 유지해야한다는 점에 유의하십시오. min-heap의 경우 "heap"속성은 루트 값이 자식 값보다 작아야합니다.

최소 힙의 비 리프 노드가 최대 항목을 보유하는 경우이 서브 트리의 하위 값이 루트 값보다 작기 때문에 루트가 현재 리프가 아닌 노드 인 서브 트리의 힙 속성이 위반됩니다 . 힙 속성을 유지하려면 루트 값을 자식 중 하나에 띄워야합니다.

"힙"속성을 위반하지 않으려면 최대 값을 유지하는 노드가 더 이상 자식을 가질 때까지 "최대"항목의 부동 상태가 계속됩니다. 따라서 '최대'항목은 항상 하위 노드가없는 노드 (예 : 리프 노드)에 있습니다.

2013-10-24 03:28:33 user2784234

간단히 답을 말하면 모순을 위해서 최대 값은 비 리프에 있다고 가정하십시오. 이는 힙 (heap) 속성을 위반하는데, 이는 힙 (heap) 속성에 대해 노드가 자식 값보다 작아야한다는 것을 요구합니다. 따라서 최대 값은 리프에 있어야합니다.

2017-04-03 19:19:49 qwr

답변