Skip to content

Heap Sort

This page provides a brief introduction to heap sort.

Definition

Heap sort (English: Heapsort) is a sorting algorithm designed using the data structure of a binary heap. The applicable data structure for heap sort is an array.

Process

Heap sort is essentially a selection sort based on a heap.

Sorting

First, build a max-heap. Then, take out the top element of the heap as the maximum value, swap it with the element at the end of the array, and maintain the properties of the remaining heap.

Next, take out the top element of the heap as the second largest value, swap it with the second-to-last element of the array, and maintain the properties of the remaining heap.

Repeat this process. After the \(n-1\)-th operation, the entire array is sorted.

Building a Binary Heap on an Array

Starting from the root node, arrange the nodes of each layer in the array.

Thus, for a node with index i in the array, the corresponding parent, left child, and right child nodes are as follows:

1
2
3
iParent(i) = (i - 1) / 2;
iLeftChild(i) = 2 * i + 1;
iRightChild(i) = 2 * i + 2;

Properties

Stability

Like selection sort, due to the swapping operations, heap sort is an unstable sorting algorithm.

Time Complexity

The best-case, average-case, and worst-case time complexities of heap sort are all \(O(n\log n)\).

Space Complexity

Since the heap can be built on the input array, this 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
28
void sift_down(int arr[], int start, int end) {
  // Calculate indices of parent and child nodes
  int parent = start;
  int child = parent * 2 + 1;
  while (child <= end) {  // Only compare when child index is within range
    // First compare the two children, choose the largest
    if (child + 1 <= end && arr[child] < arr[child + 1]) child++;
    // If parent is greater than or equal to child, adjustment is complete, exit function
    if (arr[parent] >= arr[child])
      return;
    else {  // Otherwise, swap parent and child, then compare child with grandchild
      swap(arr[parent], arr[child]);
      parent = child;
      child = parent * 2 + 1;
    }
  }
}

void heap_sort(int arr[], int len) {
  // Start sift down from the parent of the last node to complete heapify
  for (int i = (len - 1 - 1) / 2; i >= 0; i--) sift_down(arr, i, len - 1);
  // First swap the first element with the element before the already sorted part,
  // then readjust (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);
  }
}

 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
30
def sift_down(arr, start, end):
    # Calculate indices of parent and child nodes
    parent = int(start)
    child = int(parent * 2 + 1)
    while child <= end:  # Only compare when child index is within range
        # First compare the two children, choose the largest
        if child + 1 <= end and arr[child] < arr[child + 1]:
            child += 1
        # If parent is greater than or equal to child, adjustment is complete, exit function
        if arr[parent] >= arr[child]:
            return
        else:  # Otherwise, swap parent and child, then compare child with grandchild
            arr[parent], arr[child] = arr[child], arr[parent]
            parent = child
            child = int(parent * 2 + 1)


def heap_sort(arr, len):
    # Start sift down from the parent of the last node to complete heapify
    i = (len - 1 - 1) / 2
    while i >= 0:
        sift_down(arr, i, len - 1)
        i -= 1
    # First swap the first element with the element before the already sorted part,
    # then readjust (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
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用