Heap operations

Hide text Hide 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 heaps. After each operation, make sure that the heap-order property: "the parent is smaller than its child" 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


  Created Wed Jun 20 16:00:44 EEST 2007 - Powered by SVG-hut