나 자신을 가르치고있다는 시험 힙을하고 다음과 같은 질문을 가로 질러 온 : 나는 이유 중 하나 알고이 이진 트리가 힙이 아닌 이유는 무엇입니까?
91
/\
77 46
/\ \
68 81 11
"다음 이진 트리 힙이 아닌 이유 2 가지 이유를 제시" 이것은 힙의 자식이 부모의 값보다 작거나 같아야하므로 81은이 규칙을 81 > 77으로 위반하지만 다른 답변에는 확실하지 않습니다.
누군가가 명확히 할 수 있습니까?
11은 오른쪽 자식이 아닌 46의 왼쪽 자식이어야합니다.
11이 지금 있습니다. 이것이 유익한 이유는 매우 쉽게 이해할 수 있습니다. 힙의 크기가 주어지면 맨 아래 레벨의 마지막 노드가 어디에 삽입되고 삭제되는지 빨리 알아낼 수 있습니다. 배열 표현을 사용하는 경우, 마지막 요소 인 heap size - 1의 요소만큼 간단합니다. 포인터 기반의 표현을 위해, 우리는 마지막 요소로 가기 위해 왼쪽 또는 오른쪽으로 가야하는지 쉽게 결정할 수 있습니다.
힙이 완전한 2 진 트리가 아니더라도 동일한 성능을 얻는 다른 방법이있을 수 있지만 복잡성이 더해질 수 있습니다.
힙 속성을 따르지 않으므로 힙이 아닙니다.
루트 노드 (91)가 하위 노드보다 크기 때문에 분명히 최소 힙이 아닙니다. 노드 77이 오른쪽 자식 인 81보다 작기 때문에 분명히 최대 힙이 아닙니다.
그리고 @Dukeling은 답변에서 지적했듯이 shape 속성을 준수하지 않습니다.
'11'은 오른쪽 자식이 아닌 '46'의 왼쪽 자식이어야하지만 그게 중요한지 확실하지 않습니다. – Claudiu
''이 이진 트리가 힙이 아닌 이유는 무엇입니까? '와''힙 정렬 작업은 어떻게 다른가?'- 두 개를 분리 된 두 개의 질문으로 분리해야합니다. 가능성이 높다. – Dukeling
내 원래 제목이 편집되어 그 질문으로 이어 지므로 지금 해당 부분을 편집합니다. 죄송합니다. –