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 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

  Created Fri Oct 30 13:52:51 EET 2009 - Powered by SVG-hut