간단한 배경 : 삽입이 발생할 때 힙 속성을 유지 관리하는 단계를 연구하고 있습니다.힙 속성 유지
질문 : 순서 또는
?
참조 : John Edgar 박사가 작성한 http://www.cs.sfu.ca/CourseCentral/225/johnwill/cmpt225_09heaps.pdf (힙 삽입 - 슬라이드 16).
왜 위의 방법 중 하나가 더 나은지 분명히 알면 좋을 것입니다.
배열로 구현 된 바이너리 힙에서는 삽입을 구현하는 두 가지 방법, 즉 하향식 또는 상향식이 있습니다. 링크 된 PDF의 슬라이드 17은 일을하는 상향식 방법을 설명합니다. 새 항목을 힙 끝 부분에 추가 (가장 아래쪽, 가장 왼쪽 위치)하고 위로.니다. 이는 슬라이드 1에 표시된 전략 1의 구현입니다.
평균적으로 이인데 이는 성능 측면에서 더 좋은 방법입니다. 순서를 수정하는 데 필요한 반복 횟수가 더 적기 때문입니다. 그 이유에 대한 자세한 설명은 Argument for O(1) average-case complexity of heap insertion을 참조하십시오.
슬라이드 (16) 전략 (2)에 대응하는 하향식 접근, 마다 삽입 O (로그 n)의 비교를 필요. 이 전략은 루트에서 시작하여 힙을 통해 항목을 정렬합니다. 새 항목이 비교 대상 노드보다 작 으면 (최소 힙 단위) 해당 노드의 항목을 바꿉니다. 교체 된 항목은 푸시 다운되어야합니다. 이것은 힙의 맨 아래에 도달 할 때까지 계속됩니다. 리프 레벨에서 힙에 새 항목을 넣어야하기 때문에 "조기 종료"가 가능하지 않습니다.
먼저 순서를 확인한 다음 완전성을 확인하는 방법을 생각한 적이 없지만 본질적으로 하향식 방법과는 다릅니다.
두 번째 전략은 삽입 당 더 많은 반복이 필요하며 순서를 유지하기 위해 반복 할 때마다 더 많은 작업을 수행합니다.
좋습니다. 프로그램이 순서를 유지하기 위해 필요한 반복 횟수와 관련이 있습니다. 따라서 완전성을 확인한 후 주문을 수정하는 것이 가장 좋습니다. 귀하의 명확한 해 주셔서 감사합니다, 그것은 지금 나에게 의미가 있습니다 :) – Kourosh
@Kourosh : 그리고 첫 번째 경우에는 "완전성을 확인"할 필요조차 없습니다. 새 항목을 적절한 위치에 배치하면 정의에 따라 완전 함을 보장합니다. –
네가 옳다면, 우리는 완전성을 검사하지 않습니다. 삽입이 배열의 크기에서 발생하고 나서 버블 업 (즉, 재 히프 업) 알고리즘이 호출되어 항목을 올바른 위치에 배치하여 순서를 고정합니다. 또한, 교수가 삽입 후 풍선을 사용하고 삭제 후 버블 다운을 권장하는 이유를 기억합니다 (즉, 적은 작업). – Kourosh