Please enable JavaScript.
Coggle requires JavaScript to display documents.
Last Lecture CS32 (Heapsort (Efficient Heap sort (We do this by shuffling…
Last Lecture CS32
Heapsort
Efficient Heap sort
Convert input array into heap
We do this by shuffling things around until it's a heap
In this example we're using max heap
Version 1
Start at last until you get to root
For each node as you work your way up treat it as a max heap
The idea is that if you make all the sub trees a proper man heap then the whole thing is a max heap
Downside is that the leaves don't actually do anything since a single node is already a mal neap
Better Version
Start at size/2-1
This works since we're dividing the last low by 2 which gets us to the last row's parent
Big O
I
Heapify
O(n)
General
Continuously removing the max or min depending on the type of heap gives us a sorted one