Heap Sort: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(One intermediate revision by the same user not shown)
Line 3: Line 3:
* [[Algorithms#Sorting_Algorithms|Algorithms]]
* [[Algorithms#Sorting_Algorithms|Algorithms]]
* [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]]
* [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]]
* [[Heap#Overview|Heaps]]
* [[Heap#Canonical_Uses_of_a_Heap|Heaps]]


=Overview=
=Overview=


{| class="wikitable" style="text-align: left;"
{| class="wikitable" style="text-align: left;"
| [[Algorithm_Complexity#Worst-case_Running_Time|Worst-case time]] || O(n lgn)
| [[Algorithm_Complexity#Worst-case_Running_Time|Worst-case time]] || O(n log n)
|-
|-
|  [[Algorithm_Complexity#Average-case_Running_Time|Average-case time]] ||  
|  [[Algorithm_Complexity#Average-case_Running_Time|Average-case time]] ||  

Latest revision as of 23:58, 19 October 2021

Internal

Overview

Worst-case time O(n log n)
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).