Heap Sort
An Introduction
Prof. David Bernstein
James Madison University
Computer Science Department
bernstdh@jmu.edu
The Algorithm
Step 1:
All of the elements have to be organized into a
heap
Step 2:
The top element is repeatedly removed and the heap is "re-organized"
Some Observations
A Limitation:
Heap sort requires "random access" to all elements
Hence, it is really only appropriate for sorting arrays
Efficiency:
You should be able to determine the bound on the worst case time efficiency
There's Always More to Learn