The Function Heapsort

In the figure you see the function heapsort within the functional structure of the algorithm.

The function heapsort is not called by any function of the algorithm. It is the only function that is called from outside the algorithm. Therefore it serves as the entry function to the algorithm.

A program that wants to sort data using the heapsort algorithm provides the data in an array. Because of the data structure implementation the array appears to the algorithm as a heaptree. The program calls the heapsort function that sorts the data and places it in the result list. The program can then use the sorted data from the result list.

Short description

Sorts the input data.

This is the entry function of the heapsort algorithm.

Interface

The interface describes what a user of the function needs to know. It encompasses parameters, precondition and postcondition.

Parameters

Parameters determine on which part of the data structure the function shall work. Explicit parameters are passed with the function call and control the function directly. Implicit parameters are not passed to the function. They are a part of the data structure the function knows and accesses.

Precondition

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

It is not required that the nodes are heapordered!

The precondition describes under which condition the function can be called. It is phrased as a condition of the data structure.

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

The figure above shows a data structure state that fulfills the precondition.
Later on you will work with an exercise that starts with this state.

The precondition for this function is easily fulfilled, because the program using the heapsort algorithm needs only to provide input data.

Postcondition

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

The postcondition describes the functions effect. It states the logic conditions on the data structure after the function execution.

Node Meaning Size of key. Empty.

The figure above shows a state of the data structure fulfilling the postcondition. Later on you will work with an exercise where you lead the data structure to this state.

The end of the algorithms execution is reached when the heapsort function finishes. The result list then contains the sorted data.

Realisation

The realization describes the functions internal behaviour. In this courseware the realization is described mostly on an abstract level and implementation strategies are only sketched.

Helper functions

This functions calls other functions as helper functions to fullfill its duty. Below you see the interface of the helper functions.

Exercise

Now it's your turn! Find out with the help of the interactive exercise (Java Applet) below which steps this function must perform. Call the helper functions by clicking the function name buttons. The goal is to reach the state conforming the postcondition.

Operating hints

• Leaving the mouse pointer over an element of the applet for some seconds will pop up an explaining text (Tooltip).
• When you are done, press the button "check" () to approve your solution.
• It may take some minutes until the applet appears. If still no applet appears.
• Operating instructions for applets

The applet

Solution

You may be surprised that only two function calls occur here. Unlike typical text books the algorithm is structured into several small functions in this courseware. As a result each function only performs a few steps.

To see the pseudocode of the function, switch the applet to animation mode. Use the buttons at the bottom of the applet to step through the solution. Each step is accompanied with a short explaining message.

The heapsort algorithm works in two phases:

1. Build-Heap heaporders the heaptree.
2. Sort moves all the keys into the result list.

Sort can not be called first, because its precondition requires the heaptree to be heapordered.