下一页 → ← 上一页

堆排序算法（Python/Java/C/C++程序实现）

2025年5月20日 | 阅读13分钟

堆排序通过使用给定数组的元素创建最小堆或最大堆来处理元素。最小堆或最大堆表示数组的排序，其中根元素表示数组的最小或最大元素。

堆排序基本上递归执行两个主要操作：

使用数组元素构建堆 H。
重复删除在第一阶段形成的堆的根元素。

在深入了解堆排序之前，我们首先简要介绍一下堆。

什么是堆？

堆是一个完全二叉树，二叉树是每个节点最多可以有两个子节点的树。完全二叉树是指除最后一层（即叶节点）外所有层都应填满，并且所有节点都应左对齐的二叉树。

堆排序是一种原地排序算法。

算法

Heapsort(arr) {
   BuildHeap(arr)
   for j <- length(arr) downto 2 {
      exchange arr[1] <-> arr[j]
      heapsize <- heapsize -1
      Heapify(arr, 1)
}
BuildHeap(arr) {
   heapsize <- length(arr)
   for j <- floor( length / 2 ) downto 1
      Heapify(arr, j)
}
Heapify(A, j) {
   le <- left(j)
   ri <- right(j)
   if (le <= heapsize) and (arr[le] > A[j])
      largest <- le
   else
      largest <- j
   if (ri <= heapsize) and (arr[ri] > A[largest])
      largest <- ri
   if (largest != j) {
      exchange arr[j] <-> arr[largest]
      Heapify(arr, largest)
   }
}

堆排序的步骤

步骤1：将数组转换为二叉树。

步骤2：将二叉树转换为最大堆。这将确保所有父节点都大于或等于其子节点。

步骤3：将根节点（最大元素）与堆中的最后一个元素交换。这将破坏最大堆的属性。

步骤4：为了恢复最大堆的属性，调用heapify()方法。

步骤5：重复步骤3和4，直到堆被排序，并且在每次迭代中，将最后一个元素从堆中排除。

步骤6：在每次交换和heapify()调用后，确保最大堆的属性得到维护。

堆排序算法的工作原理

现在，让我们看看堆排序算法的工作原理。

步骤1：将输入数组视为二叉树。我们以a[] = {19, 4, 13, 18, 10, 12, 15}作为输入数组。

Heap Sort Algorithm

根将位于索引0。任何位于第i个索引的根的左子节点和右子节点将分别位于索引(2 * i + 1)和(2 * i + 2)。上图说明了这一点。

步骤2：应用heapify()将其转换为最大堆。它将重新排列输入数组的元素以模拟最大堆。

Heap Sort Algorithm

步骤3：现在，用堆的最后一个元素替换根元素。请注意，我们有一个元素19在其在已排序数组中的适当位置。因此，将堆大小减小1。

Heap Sort Algorithm

步骤4：观察到当前堆不遵循最大堆的属性。因此，再次应用heapify()以重新排列元素以形成最大堆。

Heap Sort Algorithm

步骤5：用堆的最顶部元素替换堆的最后一个元素。我们将得到已排序数组的倒数第二个元素放置在倒数第二个位置。因此，堆的大小也将减小1。

Heap Sort Algorithm

步骤6：再次应用heapify()以重新排列元素以遵循最大堆的属性。

Heap Sort Algorithm

步骤7：再次，将堆的最后一个元素与最顶部元素交换。我们将得到已排序数组的倒数第三个元素。

Heap Sort Algorithm

步骤8：对堆的剩余元素应用heapify()。

Heap Sort Algorithm

步骤9：交换堆的最顶部元素和最后一个元素。此时，我们已经对数组的最后四个元素进行了排序。

Heap Sort Algorithm

步骤10：通过再次应用heapify()重新排列元素以遵循最大堆。

Heap Sort Algorithm

步骤11：对堆的最顶部元素和最后一个元素进行交换。堆中只剩下最后两个元素需要排序。

Heap Sort Algorithm

步骤12：应用heapify()，然后交换元素，我们将得到所需的结果。

现在，数组已排序。

Heap Sort Algorithm

Python/Java/C/C++/C#中的堆排序实现

Python 程序

# The method rearranges the elements of the input array 
# It ensures the right child is at the index 2 * j + 2 and the left child is at 2 * j + 1
# Where j is the index where the root lies. 
# Also, this method guarantees the root node is larger than both of its children.def heapify(arr, s, j):
     # Initialize largest as root
    largest = j   
    #  left index = 2 * j + 1
    leftIdx = 2 * j + 1   
    # right index = 2 * j + 2
    rightIdx = 2 * j + 2  
    # If the left child is bigger than the root
    if leftIdx < s and arr[leftIdx] > arr[largest]:
        largest = leftIdx
    # If the right child is bigger than the largest found so far
    if rightIdx < s and arr[rightIdx] > arr[largest]:
        largest = rightIdx
    # If the root is not the largest 
    if largest != j:
        arr[j], arr[largest] = arr[largest], arr[j]  # Swap
        # heapifying the affected sub-tree recursion
        heapify(arr, s, largest)
# Main function 
def heapSort(arr):  
    s = len(arr) 
    # Building a heap (rearranging the array)
    for j in range(s // 2 - 1, -1, -1):
        heapify(arr, s, j)
    # Extract an element from the heap one by one
    for j in range(s - 1, 0, -1):    
        # Shift root to the end
        arr[0], arr[j] = arr[j], arr[0] 
        # Calling heapify on the reduced heap
        heapify(arr, j, 0)
def printArray(arr):
    for j in arr:
        print(j, end=" ")
    print()
# Driver's code
arr = [19, 4, 13, 18, 10, 12, 15] 
print("Before sorting array elements are: ")
printArray(arr)
heapSort(arr)
print("After sorting array elements are: ")
printArray(arr)

Java 程序

public class Main {
    // The method rearranges the elements of the input array 
    // it ensures the right child is at the index 2 * j + 2 and left child is at 2 * j + 1
   // where j is the index where the root lies. 
   // Also, this method guarantees the root node is larger than both of its children.
    public void heapify(int a[], int size, int j) {
        // Initialize the rt as root
        int rt = j; 
        // left index = 2 * j + 1
        int lIndex = 2 * j + 1; 
        // right index = 2 * j + 2
        int rIndex = 2 * j + 2;
        // If the left child is larger than rt
        if (lIndex < size && a[lIndex] > a[rt]) {
            rt = lIndex;
        }
        // If the right child is larger than rt so far
        if (rIndex < size && a[rIndex] > a[rt]) {
            rt = rIndex;
        }
        // If rt is not root
        if (rt != j) {
            int temp = a[j];
            a[j] = a[rt];
            a[rt] = temp;
            // heapifying the concerned sub-tree recursively
            heapify(a, size, rt);
        }
    }
    // Main method that does the Heap Sort
     void heapSort(int a[]) {
        int len = a.length;
        // Building heap (rearrangement of the array)
        for (int j = len / 2 - 1; j >= 0; j--) {
            heapify(a, len, j);
        }
        // extract an element from the heap one by one
        for (int j = len - 1; j > 0; j--) {
            // put the current root to the end
            int temp = a[0]; 
            a[0] = a[j];
            a[j] = temp;
            // On the reduced heap, invoke max heapify 
            heapify(a, j, 0);
        }
    }
    // A utility method for printing an array
    static void displayArray(int a[]) {
        for (int j = 0; j < a.length; j++) {
            System.out.print(a[j] + " ");
        }
        System.out.println();
    }
    // main method
    public static void main(String args[]) {
        int a[] = {19, 4, 13, 18, 10, 12, 15};
        System.out.println("Before sorting array elements are: ");
        displayArray(a); 
        Main obj = new Main();
        obj.heapSort(a);
        System.out.println("After sorting array elements are: ");
        displayArray(a);
    }
}

编译并运行

C++ 程序

#include <iostream>
using namespace std;
// The method rearranges the elements of the input array 
// it ensures the right child is at the index 2 * j + 2 and left child is at 2 * j + 1
// where j is the index where the root lies. 
// Also, this method guarantees the root node is larger than both of its children.
void heapify(int a[], int size, int j) {
    // Initialize the rt as root
    int rt = j; 
    // left index = 2 * j + 1
    int lIndex = 2 * j + 1; 
    // right index = 2 * j + 2
    int rIndex = 2 * j + 2;
    // If the left child is larger than rt
    if (lIndex < size && a[lIndex] > a[rt]) {
        rt = lIndex;
    }
    // If the right child is larger than rt so far
    if (rIndex < size && a[rIndex] > a[rt]) {
        rt = rIndex;
    }
    // If rt is not root
    if (rt != j) {
        int temp = a[j];
        a[j] = a[rt];
        a[rt] = temp;
        // heapifying the concerned sub-tree recursively
        heapify(a, size, rt);
    }
}
// Main method that does the Heap Sort
 void heapSort(int a[], int len) {
    // Building heap (rearrangement of the array)
    for (int j = len / 2 - 1; j >= 0; j--) {
        heapify(a, len, j);
    }
    // extract an element from the heap one by one
    for (int j = len - 1; j > 0; j--) {
        // Put the current root to the end
        int temp = a[0]; 
        a[0] = a[j];
        a[j] = temp;
        // On the reduced heap, invoke max heapify 
        heapify(a, j, 0);
    }
}
// A utility method for printing an array
static void displayArray(int a[], int len) {
    for (int j = 0; j < len; j++) {
        cout<<a[j]<<" ";
    }
    cout<<endl;
}
// main method
int main() {
    int a[] = {19, 4, 13, 18, 10, 12, 15};
    int len = sizeof(a)/sizeof(a[0]);
    cout<<"The array before sorting is: \n";
    displayArray(a, len); 
    heapSort(a, len);
    cout<<"After sorting, array elements are: \n";
    displayArray(a, len);
    return 0;
}

编译并运行

C 语言程序

#include <stdio.h>
// The method rearranges the elements of the input array 
// it ensures the right child is at the index 2 * j + 2 and left child is at 2 * j + 1
// where j is the index where the root lies. 
// Also, this method guarantees the root node is larger than both of its children.
void heapify(int a[], int size, int j) {
    // Initialize the rt as root
    int rt = j; 
    // left index = 2 * j + 1
    int lIndex = 2 * j + 1; 
    // right index = 2 * j + 2
    int rIndex = 2 * j + 2;
    // If the left child is larger than rt
    if (lIndex < size && a[lIndex] > a[rt]) {
        rt = lIndex;
    }
    // If the right child is larger than rt so far
    if (rIndex < size && a[rIndex] > a[rt]) {
        rt = rIndex;
    }
    // If rt is not root
    if (rt != j) {
        int temp = a[j];
        a[j] = a[rt];
        a[rt] = temp;
        // heapifying the concerned sub-tree recursively
        heapify(a, size, rt);
    }
}
// Main method that does the Heap Sort
 void heapSort(int a[], int len) {
    // Building heap (rearrangement of the array)
    for (int j = len / 2 - 1; j >= 0; j--) {
        heapify(a, len, j);
    }
    // Extract an element from the heap one by one
    for (int j = len - 1; j > 0; j--) {
        // Put the current root to the end
        int temp = a[0]; 
        a[0] = a[j];
        a[j] = temp;
        // On the reduced heap, invoke max heapify 
        heapify(a, j, 0);
    }
}
// A utility method for printing an array
static void displayArray(int a[], int len) {	 
    for (int j = 0; j < len; j++) {
        printf("%d ", a[j]);
    }
    printf("\n");
}
// main method
int main() {
    int a[] = {19, 4, 13, 18, 10, 12, 15};
    int len = sizeof(a)/sizeof(a[0]);
    printf("The array before sorting is: \n");
    displayArray(a, len); 
    heapSort(a, len);
    printf("After sorting array elements are: \n");
    displayArray(a, len); 
    return 0;
}

编译并运行

C# 程序

using System;
class HeapSort {
    // The method rearranges the elements of the input array 
    // it ensures the right child is at the index 2 * j + 2 and left child is at 2 * j + 1
   // where j is the index where the root lies. 
   // Also, this method guarantees the root node is larger than both of its children.
    public static void heapify(int[] a, int size, int j) {
        // Initialize the rt as root
        int rt = j; 
        // left index = 2 * j + 1
        int lIndex = 2 * j + 1; 
        // right index = 2 * j + 2
        int rIndex = 2 * j + 2;
        // If the left child is larger than rt
        if (lIndex < size && a[lIndex] > a[rt]) {
            rt = lIndex;
        }
        // If the right child is larger than rt so far
        if (rIndex < size && a[rIndex] > a[rt]) {
            rt = rIndex;
        }
        // If rt is not root
        if (rt != j) {
            int temp = a[j];
            a[j] = a[rt];
            a[rt] = temp;
            // heapifying the concerned sub-tree recursively
            heapify(a, size, rt);
        }
    }
    // Main method that does the Heap Sort
     static void heapSort(int[] a) {
        int len = a.Length;
        // Building heap (rearrangement of the array)
        for (int j = len / 2 - 1; j >= 0; j--) {
            heapify(a, len, j);
        }
        // Extract an element from the heap one by one
        for (int j = len - 1; j > 0; j--) {
            // Put the current root to the end
            int temp = a[0]; 
            a[0] = a[j];
            a[j] = temp;
            // On the reduced heap, invoke max heapify 
            heapify(a, j, 0);
        }
    }
    // A utility method for printing an array
    static void displayArray(int[] a) {
        for (int j = 0; j < a.Length; j++) {
             Console.Write(a[j] + " ");
        }
        Console.WriteLine();
    }
    // main method
    public static void Main(String[] args) {
        int[] a = {19, 4, 13, 18, 10, 12, 15};
        Console.WriteLine("Before sorting array elements are: ");
        displayArray(a); 
        heapSort(a);
        Console.WriteLine("After sorting array elements are: ");
        displayArray(a);
    }
}

编译并运行

输出

Before sorting array elements are: 
19 4 13 18 10 12 15 
After sorting array elements are: 
4 10 12 13 15 18 19

复杂度分析

现在，让我们看看堆排序在最好情况、平均情况和最坏情况下的时间复杂度。我们还将看到堆排序的空间复杂度。

时间复杂度

最好情况复杂度：当不需要排序时，即数组已经排序。堆排序的最好情况时间复杂度为O(n log n)。

平均情况复杂度：当数组元素处于混乱状态，既不是完全升序也不是完全降序。堆排序的平均情况时间复杂度为O(n log n)。

最坏情况复杂度：当数组元素需要按逆序排序时发生。这意味着，假设要按升序对数组元素进行排序，但其元素是降序的。堆排序的最坏情况时间复杂度为O(n log n)。

堆排序的时间复杂度在所有三种情况下（最好情况、平均情况和最坏情况）都是O(n log n)。具有n个元素的完全二叉树的高度是log n。

情况	时间复杂度
最佳情况	O(n logn)
平均情况	O(n log n)
最坏情况	O(n log n)

空间复杂度

堆排序的空间复杂度是O(log n)。这是因为程序中使用了递归。我们可以通过使用迭代而不是递归将其变为O(1)。

堆排序的应用

优先队列：堆排序在实现优先队列中起着重要作用，其中元素的处理是基于优先级的。
图算法：它用于像Prim的最小生成树和Dijkstra的最短路径这样的算法，这些算法依赖于堆结构以实现高效操作。
嵌入式和实时系统：堆排序提供了 consistent 的O(n log n)时间复杂度，这对于需要可预测性能的应用程序非常有利。

堆排序的优点

有效的时间复杂度：在所有情况下，堆排序的时间复杂度都是(n * log(n))，其中n是输入元素的总数。log n因子是由于二叉堆的高度，它确保即使有大量元素，排序的整体性能也很好。
内存使用：堆排序使用最小的空间（可以通过用迭代而不是递归编写heapify()方法来实现）。它只需要空间来保存需要排序的项目；除此之外，不需要额外的空间。

堆排序的缺点

不稳定：堆排序重新排列了相对顺序。因此，使其不稳定。观察上面代码中元素的交换。
开销大：堆排序中使用的常数成本比归并排序高，尽管两者的时间复杂度都是O(n*log(n))。
效率低下：由于时间复杂度中的高常数，堆排序不是很高效。如果有一个无法放入内存的巨大数组，并且分区数组比维护堆更快，则堆排序不是一个选择。在这种情况下，像归并排序或桶排序这样的算法，可以单独并行处理数组部分，效果最好。

结论

堆排序是一种原地、高效的排序算法。它的时间复杂度为O(n log n)。当内存受限或需要保证排序算法的性能与输入无关时，它非常有用。但是，它不具有自适应性且不稳定。

因此，当输入部分排序或等效元素的稳定性很重要时，它不太适用。在大多数情况下，像快速排序或归并排序这样的算法因其更好的性能和额外的特性（如稳定性）而被使用。

下一个主题基数排序

← 上一页下一页 →

相关帖子

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

关注我们

教程

Java 数据结构 C 语言 C++ 教程 C# 教程 PHP 教程 HTML 教程 JavaScript 教程 jQuery 教程 Spring 教程

面试题

Microsoft Amazon Adobe Intuit Accenture Cognizant Capgemini Wipro Tcs Infosys

在线编译器

C R C++ Php Java Html Swift Python JavaScript TypeScript

最新帖子 | 教程列表 | 隐私政策 | 关于我们 | 联系我们

© 版权所有 2011 - 2025 TpointTech.com。保留所有权利。