Language: EN FI

Exercises > MinHeap Delete

These exercises demonstrate the content of the ByTheMark service. These are meant for private individuals for learning data structures and algorithms. If you want to try out more content, you can register to the ByTheMark Personal free of charge.

MinHeap is represented both as an array and binary tree. Before doing the exercise, study the following code example, and implement operations Left-child-index(i) and Right-child-index(i) for this particular heap.

Perform DeleteMin, three times, and after each deletion, restore heap property.

Algorithm 1 Heap-Extract-Min(A)


minA[0]
A[0] ← A[heap-size[A]-1]
heap-size[A] ← heap-size[A] - 1
Min-Heapify(A, 0)
return min


Algorithm 2 Min-Heapify(A, i)


lLeft-child-index(i)
rRight-child-index(i)
if l < heap-size[A] and A[l] < A[i] then
smallestl
else
smallesti
end if
if r < heap-size[A] and A[r] < A[smallest] then
smallestr
end if
if smallest ≠ i then
Swap(A[i],A[smallest])
Min-Heapify(A, smallest)
end if

  Last modified Tue Mar 01 20:54:04 EET 2011