Page 117 [117]
OCR
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
