힙에서 임의의 노드를 삭제하려는 상황이 있는데 어떤 선택을 할 수 있습니까? 나는 우리가 마지막 노드와 힙의 첫번째 노드를 쉽게 삭제할 수 있다는 것을 안다. 그러나 마지막 노드를 삭제한다고하면 힙에서 임의 노드를 삭제하기위한 동작이 올바르게 정의되었는지 확실하지 않습니다.힙에서 임의 노드를 삭제할 수 있습니까?
_______________________
|X|12|13|14|18|20|21|22|
------------------------
이 경우에 I 12, 22이 정의되는 노드를 삭제할 수 있지만 예를 들어 임의의 노드를 삭제 13이라고 말하면서도 여전히 어떻게 든 힙의 전체 트리 속성을 유지합니다 (다른 속성과 함께).
배열에 유지 관리되는 바이너리 힙을 설명하고 있다고 가정합니다.이 상수는 A[N] <= A[N*2] 및 A[N] <= A[N*2 + 1] (최소 힙)입니다.
예인 경우 삭제 방법은 간단합니다. 삭제 된 요소를 마지막 요소로 대체하고 화면이 올바른 위치에 있는지 확인하기 위해 선별을 수행하십시오. 물론 힙의 총 항목 수를 유지하는 변수를 감소시킵니다.
힙 예제를 사용하여 작업하는 경우 전체 주문이없는 예제를 사용하는 것이 좋습니다. A[3] <= A[5]이 필요한 힙 정의에는 아무 것도 없으며 예제에 그러한 순서가있는 경우 잘못된 정보를 얻는 것이 쉽습니다.
힙에서 임의의 요소를 제거 할 수 없다고 생각합니다. 의는 (동일한 규칙 다음)이 예제를 보자 :
3, 10, 4, 15, 20, 6, 5.
을 내가 소자 (15)를 삭제하면 이제 힙이된다 :이 때문에 10의 5되는 아이의 일관성이 힙을 만드는 3, 10, 4, 5, 20, 6
.
무작위 삭제가 작동하지 않는다고 생각하는 이유는 힙에 내부 노드 (루트 또는 리프 대신)를 사용할 수 있기 때문이며 따라서 두 경로 (부모 및 자식)가 heapify (비교 대상)이므로 pop() 또는 insert()의 경우 1 경로로 변경하십시오. 여기에 뭔가 누락 된 경우 알려 주시기 바랍니다.
인수에 따르면 힙에서 맨 위 요소를 제거 할 수 없어야합니다. 맨 위 요소에는 두 개의 자식도 있습니다. 나는 네가 Anon의 대답에서 "계단 아래"의 중요성을 놓치고 있다고 생각한다. –
여기에 내가 누락 된 부분이 있다고 생각합니다. 대체되는 숫자는 필요에 따라 "실트 다운 (silt down)"또는 "실트 업 (silt up)"해야합니다 (예 : insert()는 silt를, delete()는 silt down을 따름). 그 맞습니까? – beriaanirudh
배열 기반 힙에서 무작위 삭제는 매우 비효율적입니다. 난수 위치를 찾으려면 전체 배열을 검색해야 할 수도 있습니다. 내가 맞습니까? –
@KaushikLele - 임의의 숫자 (힙에는 없을 수도 있음)의 위치를 검색하지 않습니다. 대신 임의의 위치를 선택하고 힙을 유지하는 방식으로 해당 항목을 제거합니다. – Joel