Seite 117 [117]
116 11 MULTIDIMENSIONAL EXPANSION OF THE ALGORYTHMICS...
Being motivated by user reguests, the next visualization we designed was
the heap sort choreography. This algorithm has O(n log n) time complexity too.
The data structure used is the heap, a nearly complete binary tree, where each
internal node has a greater (max-heap) or smaller (min-heap) value than any of
its children.
al5) a[(6] a[7]
Figure 11.1. Key momentums from the Heap sort AlgoRythmics choreography:
(a) the sequence to be sorted stored in a 1D array; (b) the sequence
represented as a binary tree; (c) the development of the heap property begins
(the dancers in the focus put on their hats, and their positions in the array
are highlighted); (d) the heap has been constructed (all “parents” “are bigger”
than their “children”); (e) the element that has reached its final position,
returns to the array; (f) the heap-sorted sequence