Data Structure Implementation
|
|
Data Structure Implementation |
|
The heapsort algorithm works with a heaptree and a result list. They can be stored efficiently in one array.
Heaptree and result list are stored together in one array. The array has as many elements as there are keys to sort. No additional storage space for pointers or intermediate results is needed. The beginning of the array is used by the heaptree, the remaining end by the result list (figure 1).
Figure 1: Heaptree and result list stored in one array
A program that wants to sort data with the heapsort algorithm provides it as an array. The array appears to the algorithm as a heaptree containing all keys. In the notation of figure 1 the green heaptree occupies the whole array. That is why the heaptree needs not be built but exists instantly, complete and completely filled.
The function heapsort performs the complete algorithm. Within the algorithm the function move-max moves keys from the heaptree to the result list. This removes one key from the heaptree which makes room in the array at the border between heaptree and result list. The result list grows using this free node and stores the new element there.
After the algorithm run the result list occupies the complete array. There is no need to copy this list, because the array can be used directly by the program.
The heaptree root is stored at index 1 in the array.
For a node stored at index k in the array, its left child is stored at index 2*k and its right child at index 2*k+1 (figure 2). It follows that the parent node is at index (k div 2).
Figure 2: Mapping child nodes to indices
Figure 3 shows the array indices of the heaptree nodes for the heaptree used in the courseware.
Figure 3: Array indices of heaptree nodes
You have now completed the main contents of the courseware. From the contents page you can reach exercises, where you can apply and test your new knowledge.
|
|
|