Once we have a heap, we know that the minimum element is at the root. If we print it out and delete it, the second smallest element rises to the root. Thus, by repeatedly deleting the minimum element, we can generate the values in ascending order.
It takes time n log n to create a heap and n log n to do n delete-min operations, so this gives us an n log n algorithm for sorting.
Video lecture on Heapsort and updating values in a heap, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky