방법, 최대 힙으로 새로운 값을 삽입

Question

문제 1

제가 최대 힙 [98,67,89,38,42,54,89로 (97)를 삽입 할

     98 
        /\ 
       / \ 
       67  89 
       /\ /\ 
      / \ / \ 
      38 42 54 89 
      /\ 
     / \ 
      17 25 

에게 힙 max_delete을 적용 17,25] (목록으로 표시). 저 당으로서

가 생성 힙이다 98,97,89,38,67,54,89,17,25,42]

     98 
        /\ 
       / \ 
       97  89 
       /\ /\ 
      / \ / \ 
      38 67 54 89 
      /\  | 
     / \ | 
      17 25 42 

는 문제 2

내가 원하는 heap [100,97,93,38,67,54,93,17,25,42]에 delete_max()를 두 번 적용하십시오. 날이 deletemax 작업 후 힙 당으로

    100 
        /\ 
       / \ 
       97  93 
       /\ /\ 
      / \ / \ 
      38 67 54 93 
      /\  | 
     / \ | 
      17 25 42 

은, 힙을 결과하는 것은 [93,67,93,38,42,54,25,17]

내가 따라야 할

     93 
        /\ 
       / \ 
       67  93 
       /\ /\ 
      / \ / \ 
      38 42 54 25 
      / 
     /  
      17  

입니다 삽입 및 max_delete 올바르게 힙 및 위의 답변을하고 있습니까? 올바르지 않으면 나를 안내하십시오. 이 링크에 대한

Answer 1

귀하의 답변이 정확 보면이 링크로 액세스 할 수 있습니다. 이유에 대해 자세히 살펴 보겠습니다. 다음

당신은 97을 삽입 할

[98,67,89,38,42,54,89,17,25] 

그래서 당신이 마지막에 추가하고 최대 거품을 :

[98,67,89,38,42,54,89,17,25,97] 

당신은 97을 비교 첫 번째 경우에

, 당신은 힙이 그 부모 (42)와 97이 크기 때문에, 당신은 그들을 교환 :

[98,67,89,38,97,54,89,17,25,42] 

그런 다음 다시 부모와 97를 비교합니다. 이번에는 부모님이 67 살이므로 다시 교환해야합니다. 한 번 더 비교

[98,97,89,38,67,54,89,17,25,42] 

, 당신은 부모 (98)를 삽입 한 항목보다 더 큰 것을 볼, 그래서 당신은 완료됩니다.

힙이 [100,97,93,38,67,54,93,17,25,42] 인 경우 두 개의 가장 높은 항목을 제거하려고합니다. delete_max에 대한 규칙은 루트를 힙의 마지막 항목으로 바꾼 다음 아래로 내려갑니다.

[42,97,93,38,67,54,93,17,25] 

(42)이 그 아이보다 작은, 그래서 당신은 가장 큰 아이로 교체 : 그래서, 당신은 다시 바꿀 수 있도록,

[97,42,93,38,67,54,93,17,25] 

그것은, 38 이상이다하지만보다 작은 67 :

[97,67,93,38,42,54,93,17,25] 

이제 42가 잎 수준에 있으므로 더 이상 할 일이 없습니다. 이것이 첫 번째 삭제 된 항목입니다.이제 두 번째를 제거하십시오. 루트 25을 이동 :

[25,67,93,38,42,54,93,17] 

그리고 아래로 선별 :

[93,67,25,38,42,54,93,17] // swapped with 93 
[93,67,93,38,42,54,25,17] // swapped with 93 again 

Answer 2

봐 그래서 당신은

https://cstechwiki.blogspot.in/2016/09/python-week-6-quiz-assignment-nptel.html