TRAKLA2 - MinHeap Delete

MinHeap Delete

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions 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. For each record stored into heap you can see a key that corresponds to the priority. Delete button will remove a key. In addition, by drag & dropping a key on top of another one, you can swap the records.
Heap-Extract-Min Algorithm 1 Heap-Extract-Min(A) min ← A[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) l ← Left-child-index(i) r ← Right-child-index(i) if l < heap-size[A] and A[l] < A[i] then smallest ← l else smallest ← i end if if r < heap-size[A] and A[r] < A[smallest] then smallest ← r end if if smallest ≠ i then Swap(A[i],A[smallest]) Min-Heapify(A, smallest) end if