堆排序算法
堆排序是一种基于堆数据结构的高效排序技术。
堆是一个近乎完全的二叉树，其父节点可以是最小的，也可以是最大的。根节点最小的堆称为最小堆，根节点最大的堆称为最大堆。堆排序算法的输入数据元素使用这两种方法进行处理。
堆排序算法在此过程中遵循两个主要操作 −
根据排序方式（升序或降序），使用heapify方法（本章将进一步解释）从输入数据构建堆 H。
删除根元素的根元素，并重复此操作，直到处理完所有输入元素。
堆排序算法很大程度上依赖于二叉树的 heapify 方法。那么，这个 heapify 方法是什么呢？
Heapify 方法
二叉树的heapify方法用于将树转换为堆数据结构。此方法使用递归方法对二叉树的所有节点进行堆化。
注意 − 二叉树必须始终是完全二叉树，因为它必须始终具有两个子节点。
通过应用 heapify 方法，完全二叉树将转换为最大堆或最小堆。
要了解有关堆化算法的更多信息，请点击此处
堆排序算法
如下面算法所述，排序算法首先通过调用 Build-Max-Heap 算法构建堆 ADT，然后移除根元素并将其与叶子节点上的最小值节点交换。然后应用 heapify 方法对元素进行相应的重新排列。
Algorithm: Heapsort(A) BUILD-MAX-HEAP(A) for i = A.length downto 2 exchange A[1] with A[i] A.heap-size = A.heap-size - 1 MAX-HEAPIFY(A, 1)
分析
堆排序算法是另外两种排序算法的组合：插入排序和归并排序。
与插入排序的相似之处在于，在任何时候，只有恒定数量的数组元素存储在输入数组之外。
堆排序算法的时间复杂度为O(nlogn)，与归并排序类似。
示例
让我们通过一个示例数组来更好地理解排序算法 −
| 12 | 3 | 9 | 14 | 10 | 18 | 8 | 23 |
使用 BUILD-MAX-HEAP 算法从输入数组 − 构建堆
通过交换节点重新排列获得的二叉树，以形成堆数据结构。
堆化算法
应用堆化方法，从堆中移除根节点，并将其替换为根节点的下一个直接最大值子节点。
根节点为 23，因此弹出 23并且 18 被设为下一个根节点，因为它是堆中的下一个最大节点。
现在，18 在 23 之后弹出，并被 14 替换。
当前根节点 14 从堆中弹出，并被 12 替换。
12 被弹出并被 10 替换。
类似地，所有其他元素都使用相同的过程弹出。
这里，当前根元素 9 被弹出，元素 8 和 3 保留在树中。
然后，元素 8 将被弹出，元素 3 留在树中。
对给定的元素完成堆排序操作后堆，排序后的元素显示如下 −
由于形成的堆数据结构是最大堆，因此每次弹出元素时，都会将其添加到输出数组的开头。但是，如果 heapify 方法将二叉树转换为最小堆，则将弹出的元素添加到输出数组的末尾。
最终排序后的列表为：
| 3 | 8 | 9 | 10 | 12 | 14 | 18 | 23 |
实现
堆排序实现的逻辑是：首先，基于最大堆属性构建堆数据结构，即父节点的值必须大于子节点的值。然后，从堆中弹出根节点，并将堆中的下一个最大节点移至根节点。该过程不断迭代，直到堆为空。
在本教程中，我们将展示四种不同编程语言的堆排序实现。
#include <stdio.h>
void heapify(int[], int);
void build_maxheap(int heap[], int n){
int i, j, c, r, t;
for (i = 1; i < n; i++) {
c = i;
do {
r = (c - 1) / 2;
if (heap[r] < heap[c]) { // 创建 MAX 堆数组
t = heap[r];
heap[r] = heap[c];
heap[c] = t;
}
c = r;
} while (c != 0);
}
printf("Heap array: ");
for (i = 0; i < n; i++)
printf("%d ", heap[i]);
heapify(heap, n);
}
void heapify(int heap[], int n){
int i, j, c, root, temp;
for (j = n - 1; j >= 0; j--) {
temp = heap[0];
heap[0] = heap[j]; // 交换最大元素和最右边的叶元素
heap[j] = temp;
root = 0;
do {
c = 2 * root + 1; // 根元素的左节点
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[root]<heap[c] && c<j) { // 再次重新排列为最大堆数组
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
} while (c < j);
}
printf("
The sorted array is: ");
for (i = 0; i < n; i++)
printf("%d ", heap[i]);
}
int main(){
int n, i, j, c, root, temp;
n = 5;
int heap[10] = {2, 3, 1, 0, 4}; //初始化数组
build_maxheap(heap, n);
}
输出
Heap array: 4 3 1 0 2 The sorted array is: 0 1 2 3 4
#include <iostream>
using namespace std;
void heapify(int[], int);
void build_maxheap(int heap[], int n){
int i, j, c, r, t;
for (i = 1; i < n; i++) {
c = i;
do {
r = (c - 1) / 2;
if (heap[r] < heap[c]) { // 创建 MAX 堆数组
t = heap[r];
heap[r] = heap[c];
heap[c] = t;
}
c = r;
} while (c != 0);
}
cout << "Heap array: ";
for (i = 0; i < n; i++)
cout <<heap[i]<<" ";
heapify(heap, n);
}
void heapify(int heap[], int n){
int i, j, c, root, temp;
for (j = n - 1; j >= 0; j--) {
temp = heap[0];
heap[0] = heap[j]; // 交换最大元素和最右边的叶元素
heap[j] = temp;
root = 0;
do {
c = 2 * root + 1; // 根元素的左节点
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[root]<heap[c] && c<j) { // 再次重新排列为最大堆数组
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
} while (c < j);
}
cout << "
The sorted array is : ";
for (i = 0; i < n; i++)
cout <<heap[i]<<" ";
}
int main(){
int n, i, j, c, root, temp;
n = 5;
int heap[10] = {2, 3, 1, 0, 4}; //初始化数组
build_maxheap(heap, n);
return 0;
}
输出
Heap array: 4 3 1 0 2 The sorted array is : 0 1 2 3 4
import java.io.*;
public class HeapSort {
static void build_maxheap(int heap[], int n) {
for (int i = 1; i < n; i++) {
int c = i;
do {
int r = (c - 1) / 2;
if (heap[r] < heap[c]) { // 创建 MAX 堆数组
int t = heap[r];
heap[r] = heap[c];
heap[c] = t;
}
c = r;
} while (c != 0);
}
System.out.println("Heap array: ");
for (int i = 0; i < n; i++) {
System.out.print(heap[i] + " ");
}
heapify(heap, n);
}
static void heapify(int heap[], int n) {
for (int j = n - 1; j >= 0; j--) {
int c;
int temp = heap[0];
heap[0] = heap[j]; // 交换最大元素和最右边的叶元素
heap[j] = temp;
int root = 0;
do {
c = 2 * root + 1; // 根元素的左节点
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[root]<heap[c] && c<j) { // 再次重新排列为最大堆数组
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
} while (c < j);
}
System.out.println("
The sorted array is: ");
for (int i = 0; i < n; i++) {
System.out.print(heap[i] + " ");
}
}
public static void main(String args[]) {
int heap[] = new int[10];
heap[0] = 4;
heap[1] = 3;
heap[2] = 1;
heap[3] = 0;
heap[4] = 2;
int n = 5;
build_maxheap(heap, n);
}
}
输出
Heap array: 4 3 1 0 2 The sorted array is: 0 1 2 3 4
def heapify(heap, n, i):
maximum = i
l = 2 * i + 1
r = 2 * i + 2
# if left child exists
if l < n and heap[i] < heap[l]:
maximum = l
# if right child exits
if r < n and heap[maximum] < heap[r]:
maximum = r
# root
if maximum != i:
heap[i],heap[maximum] = heap[maximum],heap[i] # swap root.
heapify(heap, n, maximum)
def heapSort(heap):
n = len(heap)
# maxheap
for i in range(n, -1, -1):
heapify(heap, n, i)
# 元素提取
for i in range(n-1, 0, -1):
heap[i], heap[0] = heap[0], heap[i] # swap
heapify(heap, i, 0)
# main
heap = [4, 3, 1, 0, 2]
heapSort(heap)
n = len(heap)
print("Heap array: ")
print(heap)
print ("The Sorted array is: ")
print(heap)
输出
Heap array: [0, 1, 2, 3, 4] The Sorted array is: [0, 1, 2, 3, 4]
