Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps, Heapsort - Coggle Diagram
Heaps
Properties
-
-
A heap can be implemented as an array by recording its element in top-to-down/left-to-right fashion, usually starting by the position 1
Parental key nodes in the first (ceil)n/2 positions, while the leaf gets the rest of it
If a parent is in position i, its children will be in position 2i and 2i + 1
There's exactly one essentially complete binary tree with n nodes. Its height is equal to the ceil of log2(n)
-
-
-
Heapsort
Stages
-
-
Result
The array elements will be eliminated in decreasing order, but in the root deletion algorithm, the item being deleated is placed last. So grabbing those deleted items will make your sorted array
-
Analysis
-
It's pretty competitive with mergesort, but with no extra space required. Quicksort still faster in average.
