How to "heapify" array based min heap after remove min?

Question

How would I "heapify" an array based minimum heap in java once the remove min function has been called (this simply takes the element at index 1 and removes it, and then replaces it with the last item in the array). I'm confused as to how I would go about putting the array into a minimum heap again after the remove min has happened.

The index 0 is always kept empty in the heap minimum array. The parent index is i/2, the right child is 2i + 1, and the left child is 2i.

Any help would be much appreciated, thanks guys!

Answer 1

Take the last element and copy it to the first position. Reduce heapsize by one and call heapify() on the first element. The heap should repair itself. This has complexity of 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)