min을 제거한 후 배열 기반 min 힙을 "heapify"하는 방법은 무엇입니까?

Question

제거 min 함수가 호출 된 후 Java에서 배열 기반 최소 힙을 "heapify"하는 방법 (이 작업은 인덱스 1의 요소를 가져 와서 제거한 다음 배열의 마지막 항목으로 바꿉니다). 제거 작업이 완료된 후 배열을 다시 최소 힙에 넣는 방법에 대해 혼란 스럽습니다.

인덱스 0은 항상 힙 최소 배열에서 비어 있습니다. 부모 색인은 i/2이고, 오른쪽 자식은 2i + 1이고, 왼쪽 자식은 2i입니다.

도움이 될 것입니다, 고마워요!

Answer 1

마지막 요소를 가져 와서 첫 번째 위치로 복사하십시오. 힙을 하나씩 줄이고 첫 번째 요소에 heapify()을 호출하십시오. 힙은 스스로 복구해야합니다. 이것은 O (log n)의 복잡성을 가지고 있습니다

Min-Heapify-Down (Array A, int i): 
    left ← 2i 
    right ← 2i + 1 
    smallest ← i 

    if left ≤ heap_length[A] and A[left] < A[smallest] then: 
     smallest ← left 
    if right ≤ heap_length[A] and A[right] < A[smallest] then: 
     smallest ← right 

    if smallest ≠ i then: 
     swap A[i] ↔ A[smallest] 
     Min-Heapify-Down(A, smallest)