CODEWITHSUNDEEP
algorithmdata-structuresheap
FoolishNumber
FoolishNumber

Reputation: 39

MinHeap Delete Understanding

I am having difficulty in understanding the solutions of one of the problems my professor gave me regarding heaps.

Give pseudocode for the routine Min-Heap-Delete(A, k). Assume that key k is at location l of the heap and that 1 ≤ l ≤ n.

My solution is that

Exchange A[k] with A[A.size() - 1]

A.size() = A.size() - 1

Min-heapify(A,k)

However, my solution has a difference with the professor's in the first part.

Exchange A[k] with A[A.heap_size()]

A.heap_size() = A.heap_size() - 1

Min-heapify(A,k)

Why would we use A.size() instead of A.size() - 1? Wouldn't A.size() over index the array that represent the heap since heap starts at index 1?

enter image description here

In this case, A.size() would give us 10. However, A[10] doesn't exist and would cause an error. Therefore, why isn't it A[10-1] to obtain the last node in the heap tree?

Upvotes: 0

Views: 226

Answers (1)

MBo
MBo

Reputation: 80327

Because professor uses 1-based numeration instead of zero-based. Note 1 ≤ l ≤ n condition. And you probably missed that index is A.heap_size - heap size rather than array size, so last element will be referred as A[9]

It is rather common practice and convenient for heaps because child/parent index relations look very simple:

childs = parent * 2 and parent * 2 + 1
parent = child / 2

Note that array at the picture is really zeo-based with unused zero entry

Upvotes: 2

Related Questions