Heap Sort: Difference between revisions
Jump to navigation
Jump to search
| Line 17: | Line 17: | ||
=Algorithm= | =Algorithm= | ||
For each element we need to sort, insert it in a [[Heap#Min_Heap_and_Max_Heap|min heap]], using the heap's <tt>[[Heap#INSERT|INSERT]]</tt> operation. The running time of an individual <tt>INSERT</tt> is O(log n), so the insertion in a loop will have a running time of O(n log n). Once all the elements that need to be sorted are placed in the min heap, extract the minimum element from the heap, also in a loop, and place it in order in the final array. The running time of the second phase is O(n log n). The total running time is O(n log n). | For each element we need to sort, insert it in a [[Heap#Min_Heap_and_Max_Heap|min heap]], using the heap's <tt>[[Heap#INSERT|INSERT]]</tt> operation. The running time of an individual <tt>INSERT</tt> is O(log n), so the insertion in a loop will have a running time of O(n log n). Once all the elements that need to be sorted are placed in the min heap, extract the minimum element from the heap, also in a loop, with <tt>[[Heap#REMOVE-MIN|REMOVE-MIN]]</tt> and place it in order in the final array. The running time of the second phase is O(n log n). The total running time is O(n log n). | ||
Revision as of 22:15, 9 October 2021
Internal
Overview
| Worst-case time | O(n lgn) |
| Average-case time | |
| Best-case time |
Algorithm
For each element we need to sort, insert it in a min heap, using the heap's INSERT operation. The running time of an individual INSERT is O(log n), so the insertion in a loop will have a running time of O(n log n). Once all the elements that need to be sorted are placed in the min heap, extract the minimum element from the heap, also in a loop, with REMOVE-MIN and place it in order in the final array. The running time of the second phase is O(n log n). The total running time is O(n log n).