上查看所有课程
堆排序是计算机编程中一种流行且高效的排序算法。学习如何编写堆排序算法需要了解两种数据结构——数组和树。
我们想要排序的初始数字集存储在一个数组中，例如 [10, 3, 76, 34, 23, 32]，排序后得到一个已排序的数组 [3,10,23,32,34,76]。
堆排序通过将数组的元素可视化为一种特殊的完全二叉树——堆——来工作。
数组索引与树元素之间的关系
完全二叉树有一个有趣的属性，我们可以利用它来查找任何节点的子节点和父节点。
如果数组中任何元素的索引是 i，则索引为 2i+1 的元素将成为左子节点，索引为 2i+2 的元素将成为右子节点。同样，索引为 i 的任何元素的父节点由 (i-1)/2 的下取整给出。
让我们来测试一下，
Left child of 1 (index 0) = element in (2*0+1) index = element in 1 index = 12 Right child of 1 = element in (2*0+2) index = element in 2 index = 9 Similarly, Left child of 12 (index 1) = element in (2*1+1) index = element in 3 index = 5 Right child of 12 = element in (2*1+2) index = element in 4 index = 6
我们还确认一下这些规则是否适用于查找任何节点的父节点。
Parent of 9 (position 2) = (2-1)/2 = ½ = 0.5 ~ 0 index = 1 Parent of 12 (position 1) = (1-1)/2 = 0 index = 1
理解数组索引到树位置的这种映射对于理解堆数据结构如何工作以及如何用于实现堆排序至关重要。
什么是堆数据结构？
堆是一种特殊的基于树的数据结构。如果一棵二叉树满足以下条件，则称其遵循堆数据结构：
- 它是一棵完全二叉树。
- 树中的所有节点都遵循一个属性，即它们都大于它们的子节点，也就是说，最大的元素位于根节点，其两个子节点都小于根节点，依此类推。这样的堆称为最大堆。反之，如果所有节点都小于它们的子节点，则称为最小堆。
以下示例图显示了最大堆和最小堆。
要了解更多信息，请访问堆数据结构。
如何“堆化”一棵树
从一棵完全二叉树开始，我们可以通过在堆的所有非叶子节点上运行一个称为堆化（heapify）的函数来将其修改为最大堆。
由于堆化使用递归，它可能难以理解。所以我们先来考虑如何堆化一棵只有三个节点的树。
heapify(array)
Root = array[0]
Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
if(Root != Largest)
Swap(Root, Largest)
上面的例子显示了两种情况——一种是根节点是最大的元素，我们不需要做任何事情；另一种是根节点有一个更大的子节点，我们需要进行交换以维护最大堆属性。
如果您之前处理过递归算法，您可能已经识别出这必须是基本情况。
现在让我们考虑另一种情况，即存在多个层级。
顶层元素不是最大堆，但所有子树都是最大堆。
为了维护整个树的最大堆属性，我们需要不断地将 2 向下推，直到它到达正确的位置。
因此，为了在两个子树都是最大堆的树中维护最大堆属性，我们需要反复对根节点运行堆化，直到它比它的子节点大，或者它成为一个叶子节点。
我们可以将这两种情况合并到一个堆化函数中，如下所示：
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}该函数同时适用于基本情况和任意大小的树。因此，只要子树是最大堆，我们就可以移动根元素到正确的位置，以维持任何树大小的最大堆状态。
构建最大堆
因此，要从任何树构建最大堆，我们可以从下往上开始堆化每个子树，并在函数应用于所有元素（包括根节点）后得到一个最大堆。
在完全二叉树的情况下，非叶子节点的第一个索引是 n/2 - 1。之后的所有其他节点都是叶子节点，因此不需要堆化。
所以，我们可以这样构建一个最大堆：
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
如上图所示，我们从堆化最小的子树开始，然后逐渐向上移动，直到到达根节点。
如果您到目前为止都理解了，恭喜您，您正在迈向掌握堆排序的道路。
堆排序的工作原理
- 由于树满足最大堆属性，最大的元素就存储在根节点。
- 交换：移除根节点并将其放到数组的末尾（第 n 个位置）。将树（堆）的最后一个元素放到空出的位置。
- 移除：将堆的大小减 1。
- 堆化：再次堆化根节点，以便我们能在根节点获得最大的元素。
- 这个过程会重复进行，直到列表中的所有元素都被排序。
下面的代码展示了该操作。
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}Python、Java 和 C/C++ 中的堆排序代码
# Heap Sort in python
def heapify(arr, n, i):
# Find largest among root and children
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
# If root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build max heap
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
# Heapify root element
heapify(arr, i, 0)
arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print("%d " % arr[i], end='')
// Heap Sort in Java
public class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Heap sort
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify root element
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
// Swap and continue heapifying if root is not largest
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
// Function to print an array
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver code
public static void main(String args[]) {
int arr[] = { 1, 12, 9, 5, 6, 10 };
HeapSort hs = new HeapSort();
hs.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}// Heap Sort in C
#include <stdio.h>
// Function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}
// Print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code
int main() {
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is \n");
printArray(arr, n);
}// Heap Sort in C++
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}
// Print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver code
int main() {
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}堆排序复杂度
| 时间复杂度 | |
|---|---|
| 最佳 | O(nlog n) |
| 最坏 | O(nlog n) |
| 平均 | O(nlog n) |
| 空间复杂度 | O(1) |
| 稳定性 | 否 |
堆排序在所有情况下（最好、平均和最坏情况）的时间复杂度都是 O(nlog n)。
让我们来理解原因。包含 n 个元素的完全二叉树的高度是 log n。
正如我们之前看到的，为了完全堆化一个子树已经是最大堆的元素，我们需要不断地将该元素与其左子节点和右子节点进行比较，并将其向下推，直到它到达一个其两个子节点都比它小的位置。
在最坏的情况下，我们需要将一个元素从根节点移动到叶子节点，这会产生 log(n) 次比较和交换。
在构建最大堆阶段，我们对 n/2 个元素执行此操作，因此构建堆步骤的最坏情况复杂度是 n/2*log n ~ nlog n。
在排序步骤中，我们交换根节点和最后一个元素，然后堆化根节点。对于每个元素，这再次需要 log n 的最坏时间，因为我们可能需要将元素从根一直带到叶子。由于我们重复此操作 n 次，因此堆排序步骤也是 nlog n。
此外，由于 build_max_heap 和 heap_sort 步骤是依次执行的，因此算法复杂度不会相乘，它仍然保持在 nlog n 的数量级。
它还以 O(1) 的空间复杂度执行排序。与快速排序相比，它具有更好的最坏情况（O(nlog n)）。快速排序的最坏情况复杂度为 O(n^2)。但在其他情况下，快速排序更快。Introsort 是堆排序的一种替代方案，它结合了快速排序和堆排序的优点，保留了它们的优势：堆排序的最坏情况速度和快速排序的平均速度。
堆排序的应用
关注安全性以及嵌入式系统的系统，例如 Linux 内核，因为堆排序具有 O(n log n) 的运行时间上限和 O(1) 的辅助存储空间上限，所以会使用堆排序。
尽管堆排序即使在最坏情况下也具有 O(n log n) 的时间复杂度，但与快速排序、归并排序等其他排序算法相比，它的应用并不多。然而，它的底层数据结构——堆——可以在不额外维护剩余项已排序顺序的开销下，高效地用于提取列表中的最小（或最大）项。例如优先级队列。