## Heap operations

 Hide textShow text Hide pseudo-codeShow pseudo-code Search the k''th smallest element by the following algorithm. First, insert the given keys (Stream of Keys) one by one into the Heap below. Second, delete k=3 times the smallest element from the heap. After each operation, make sure the heap property the parent is smaller than its children is preserved. Some additional problems. Algorithm 1 Select(Stream of keys, k) for each key in Stream of keys do Heap-Insert(A, key) end for for i ← 1 to k do r = Heap-Extract-Min(A) end for return r Algorithm 2 Heap-Insert(A, key) heap-size[A] ← heap-size[A] + 1 i ← heap-size[A] while i > 1 and A[Parent(i)] > key do A[i] ← A[Parent(i)] i ← Parent(i) A[i] ← key Algorithm 3 Heap-Extract-Min(A) min ← A[1] A[1] ← A[heap-size[A]] heap-size[A] ← heap-size[A] - 1 Min-Heapify(A, 1) return min Algorithm 4 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