Selection Trees

A selection tree is a complete binary tree in which the leaf nodes hold a set of keys, and each internal node holds the “winner” key among its children.

Modifying a Key

It takes O(log n) time to modify a selection tree in response to a change of a key in a leaf.

   

Initialization

The construction of a selection tree from scratch takes O(n) time by traversing it level-wise from bottom up.

   

Application: External Sort

Given a set of n values	16 9 10 8 6 11 12 1 4 7 14 13 2 15 5 3				n = 16
divide it into M chuncks,	16 9 10 8	6 11 12 1	4 7 14 13	2 15 5 3	M = 4
internally sort each chunk,	8 9 10 16	1 6 11 12	4 7 13 14	2 3 5 15
construct complete binary tree of M leaves with the chunks attached to the leaves.
Convert the tree into a selection tree with the keys being fed to the leaves from the chunks
Remove the winner from the tree
Feed to the empty leaf the next value from its corresponding chunk
Adjust the selection tree to the change in the leaf
Repeat the deletion subprocess until all the values are consumed.

• The algorithm takes  time to internally sort the elements of the chunks, O(M) to initialize the selection tree, and O(n log M) to perform the selection sort. For M « n the total time complexity is O(n logn).
• To reduce I/O operations, inputs from the chunks to the selection tree should go through buffers.