노드 A를 [I]는 맥스 힙

Question

CLRS 운동에서 삭제 : 6.5-8

동작 HEAP-DELETE(A,i) 힙 A에서 노드 i 내의 아이템을 삭제한다. n 요소 최대 힙에 대해 O(lg n) 시간 실행되는 HEAP-DELETE 구현을 제공하십시오. 알고리즘은 입력 A[10]={84,22,19,21,3,10,6,5,20} 잘못 (지수가 1로 시작)와 삭제되는 A[6]=10와 경우

이 궁금하다. 마지막 노드를 A[6]으로 바꾸면 힙 값이 무시되고 힙 속성을 위반하게됩니다.

나는이 알고리즘을 작성했는데 제대로 작동하는지, 어디서 잘못되었는지 알고 싶었습니까? = - - 1

그리고 실제로 "속성 인 경우

A.heapsize을 : 그것은 오타,하지만 당신이 실제로 여기 증가 것처럼 보이는 경우

HEAP-DELETE(A,i) 
    A[i]=A[A.heapsize] 
    A.heapsize-=1 
    while i>1 and A[parent(i)]<A[i] 
    swap A[i] with A[parent(i)] 
    i=parent(i); 

Answer 1

최대 힙에서 노드를 삭제할 때 가장 먼저해야 할 일은 대상 요소를 마지막 요소로 교체 한 다음 마지막 요소를 삭제하는 것입니다.

이제 우리는 요소를 주변에서 움직여서 최대 힙을 수정하는 문제에 직면하게됩니다. 방금 이동 한 요소를 x이라고 부릅니다.

세 가지 경우가 있습니다

• x는
• x는
• x 부모와 동일한 부모보다 작은 부모보다 큰

x의 경우와 동일 부모님, 쉽습니다. 우리는 아무 것도하지 않습니다. x 부모보다 작은 경우

은, 우리가해야 할 일은 우리가 x 아래의 실수를 수정해야하기 때문에, (나는 당신이 그 의견에서 어떻게 작동하는지 이해 있으리라 믿고있어)를 MAX-HEAPIFY이다.

x이 부모보다 큰 경우 문제가 발생합니다. 이것을 처리하는 것은 너무 까다 롭지 않습니다. x을 부모와 비교하기 만하면됩니다. x이 부모보다 큰 경우 스왑합니다. x이 부모보다 더 이상 존재하지 않거나 우리가 루트에 도달 할 때까지이 프로세스를 계속하십시오 (x에 부모가없는 경우).

당신이 게시 한 의사 코드가 나에게 맞는 것처럼 보입니다. 잘 했어 :)

Answer 2

확실하지 않음 "배열 A에 대해, 나는 당신이 그것을 바꿀 수 있다고 생각하지 않는다. 그러나 나는 잘못 될 수있다. 물론, 만약 당신이 가지고있는 변수가 있다면 괜찮습니다.

이외의 의사 코드는 적어도 작동 순서에있는 것 같습니다. 여전히 작동하지 않는다면 전체 코드를 게시 할 수 있습니까?

Answer 3

이 의사 코드입니다 : 당신의 최대 힙이 있습니다, 여기에

HEAP-DELETE(A, i): 
    A[i] = A[A.heap-size] 
    A.heap-size -= 1 
    // Case : 8, 7 3, 5 6 1 2, 4 and delete 1 
    while(i > 1 and A[Parent(i)] < a[i]) 
     swap A[i] with A[parent(i)] 
     i = Parent(i) 
    // Case : 10, 9 6, 8 7 5 4, 3 and delete 6 
    MAX-HEAPIFY(A, i) 

Answer 4

간단한 버전, 당신은 내가 위치에있는 요소를 삭제하려면

DELETE(A, i) 
    HEAP-INCREASE-KEY(A, i, A[0]+1) 
    HEAP-EXTRACT-MAX(A) 

HEAP-INCREASE-KEY가 작동하는 방법은 다음과 같습니다. 삭제하려는 요소의 값을 루트보다 크게하려면 요소를 힙 루트로 가져 와서 HEAP-EXTRACT-MAX를 호출합니다. , 힙 (삭제하고자하는 요소)은 힙에서 삭제 (및 반환)됩니다