This page briefly introduces heapsort.
Definition
Heapsort is a sorting algorithm designed using a binary heap. The data structure suited to heapsort is an array.
Process
The essence of heapsort is selection sort built on a heap.
Sorting
First build a max-heap, then remove the element at the top of the heap, use it as the maximum, swap it with the element at the end of the array, and maintain the remaining heap property;
Then remove the element at the top of the heap, use it as the second largest value, swap it with the second-to-last element of the array, and maintain the remaining heap property;
Continuing in this way, the entire array is sorted after the -th operation.
Building a binary heap on an array
Starting from the root node, arrange the nodes of each level in the array in order.
Thus, for the node whose index in the array is i, its parent, left child, and right child are as follows:
iParent(i) = (i - 1) / 2;
iLeftChild(i) = 2 * i + 1;
iRightChild(i) = 2 * i + 2;
Properties
Stability
Like selection sort, it is an unstable sorting algorithm because of the operations that swap positions.
Time complexity
The best-case, average-case, and worst-case time complexities of heapsort are all .
Space complexity
Since a heap can be built in the input array, this is an in-place algorithm.
Implementation
C++
void sift_down(int arr[], int start, int end) {
// Calculate the indices of the parent and child nodes
int parent = start;
int child = parent * 2 + 1;
while (child <= end) { // Compare only when the child index is within the range
// First compare the two child nodes and choose the larger one
if (child + 1 <= end && arr[child] < arr[child + 1]) child++;
// If the parent is larger than the child, adjustment is complete; exit the function directly
if (arr[parent] >= arr[child])
return;
else { // Otherwise swap the parent and child contents, then compare the child with its grandchildren
swap(arr[parent], arr[child]);
parent = child;
child = parent * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
// Start from the parent of the last node and sift down to complete heapification (heapify)
for (int i = (len - 1 - 1) / 2; i >= 0; i--) sift_down(arr, i, len - 1);
// Swap the first element with the element immediately before the sorted elements, then readjust (the elements before the just-adjusted element) until sorting is complete
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
sift_down(arr, 0, i - 1);
}
}
Python
def sift_down(arr, start, end):
# Calculate the indices of the parent and child nodes
parent = int(start)
child = int(parent * 2 + 1)
while child <= end: # Compare only when the child index is within the range
# First compare the two child nodes and choose the larger one
if child + 1 <= end and arr[child] < arr[child + 1]:
child += 1
# If the parent is larger than the child, adjustment is complete; exit the function directly
if arr[parent] >= arr[child]:
return
else: # Otherwise swap the parent and child contents, then compare the child with its grandchildren
arr[parent], arr[child] = arr[child], arr[parent]
parent = child
child = int(parent * 2 + 1)
def heap_sort(arr, len):
# Start from the parent of the last node and sift down to complete heapification (heapify)
i = (len - 1 - 1) / 2
while i >= 0:
sift_down(arr, i, len - 1)
i -= 1
# Swap the first element with the element immediately before the sorted elements, then readjust (the elements before the just-adjusted element) until sorting is complete
i = len - 1
while i > 0:
arr[0], arr[i] = arr[i], arr[0]
sift_down(arr, 0, i - 1)
i -= 1