|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)
Algorithm 2 Heap-Insert(A, key)
Algorithm 3 Heap-Extract-Min(A)