The Function Sort

sort in structure

Short description

Moves all keys from the heaptree into the result list.

Interface

Parameters

Explicit parameters:	- (none).
Implicit parameters:	Heaptree, result list.

Precondition

Heaptree: complete, completely filled and heapordered.
Result list: empty.

Node	Meaning
	Satisfies the heap order.
	Empty.

Postcondition

Heaptree: empty.
Result list: ascending order and completely filled.

Node	Meaning
	Empty.
	Size of key.

Realisation

Helper functions

Function (Parameter)	Short description	Precondition
Move-Max ()	Moves the maximum key from the heaptree to the result list.	Heaptree: complete and heapordered. Result list: ordered ascendingly.

Exercise

Move all keys into the result list.

Operating hints

It may take some minutes until the applet appears. If still no applet appears.
Operating instructions for applets

The applet

Error: Your browser does not support JAVA!

Solution

Permitted sequences: There is only one valid sequence for this function.

The standard procedure: Move-Max removes the greatest key from the heaptree and inserts it in front of the elements of the result list. Move-Max is called as many times as there are keys in the heaptree. This generates an ascending sorted list.

Run time: Move-Max: Number of nodes.

Correctness: Follows from the correctness of move-max.