Heapsort
This page gives a brief introduction to heapsort.
Definition
Heapsort is a sorting algorithm designed around the binary heap data structure. It operates on arrays.
Procedure
Heapsort is essentially selection sort built on a heap.
Sorting
First build a max-heap. Then take the element at the top of the heap, which is the maximum, swap it with the element at the end of the array, and restore the heap property of the remaining heap.
Next, take the element at the top of the heap, which is the second largest, swap it with the second-to-last element of the array, and restore the heap property of the remaining heap.
Continue in the same way: after operation number \(n-1\), the whole array is sorted.
Building a binary heap on an array
Starting from the root, lay the nodes out in the array one level after another.
The parent, left child and right child of the node at index i of the array are then:
1 2 3 | |
Properties
Stability
As in selection sort, the swaps in heapsort can change the relative order of equal elements, so it is an unstable sorting algorithm.
Time complexity
The worst-case time complexity of heapsort is \(O(n\log n)\).
Space complexity
The heap can be built on the input array itself, so heapsort is an in-place algorithm.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | |
External links
- Heapsort - Wikipedia, the free encyclopedia (in Chinese)
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: partychicken, 24OI-bot, sshwy, ouuan, NachtgeistW, Enter-tainer, minghu6, iamtwz, Xeonacid, CamberLoid, ksyx, Ir1d, Menci, shawlleyw, Tiphereth-A, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.