The Function Build-Heap

Short description

Heaporders the complete heap tree.

Interface

Parameters

Precondition

Heaptree: complete and fully filled.

Node Meaning Possibly violates the heap order. Satisfies the heap order.

Postcondition

Heaptree: complete, fully filled and heapordered.

Node Meaning Satisfies the heap order.

Realisation

Helper functions

Exercise

Operating hints

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

The applet

Solution

The leave nodes are heapordered, because they have no child nodes that could violate the heaporder.

You calculate the position of the last inner node by going from the last node to its parent node. A node is an inner node, if it is not a leaf node.

Permitted Sequences: You can only call Heapify at a node, if both child trees under the node are already heapordered. There are several sequences of Heapify calls that obey this rule. The simulation mode allows all valid sequences. Already in the first step you can choose between two nodes: the leftmost node in the third level from above and the right node in the second level.

Need for a standard procedure: Algorithm functions must obey the preconditions of their helper functions. In the general case there are several valid sequences of calls to helper functions. To be able to execute an algorithm as a program, one sequence must be chosen. This sequence is called Standard Procedure here. One chooses a sequence that is efficient (needs few steps) and is easy to program.

The standard procedure starts at the last inner node and moves through the levels from bottom to top. Within a level it moves from right to left. This ensures, that the child trees of a node are heap ordered, when Heapify is called. Because of the implementation of the data structure this can be programmed as a simple iteration (with integer decrement). You can study the standard procedure with the "Animation mode".

Learning concept: In a typical text book you are only taught the standard procedure. In this courseware you are also informed about (and can find out yourself) the background, how the standard procedure was developed. That is why you shall think about which steps a function might perform and in what sequence. (More about the learning concept).

Modes of the applet: In this applet you can see the differences between the modes Simulation, Practice and Animation especially well. Try out the different modes now. Solve the Applet in the mode Practice. It will only let you perform the steps of the standard procedure. (More about the applet operating instructions).