Heap Sort in Java

2025年4月2日 | 阅读9分钟

堆排序使用一种基于比较的算法，该算法将输入数组视为一个堆。堆通常是最大堆（二叉堆）。堆排序可以看作是选择排序的一种优化。

堆排序算法的工作原理

让我们举个例子来理解堆排序的工作原理。

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

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

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

步骤3：现在，将根元素与堆的最后一个元素进行交换。请注意，元素19已在其在已排序数组中的正确位置。因此，将堆大小减1。

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

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

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

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

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

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

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

步骤11：应用堆的最高元素和最后一个元素的交换。此时，堆中仅剩最后两个元素需要排序。

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

使用递归实现

算法

HEAP_SORT(array):
    n = length(array)
    // Step 1: Build the max-heap
    FOR i FROM n / 2 - 1 TO 0:
        HEAPIFY(array, n, i)
    // Step 2: Sort the array
    FOR i FROM n - 1 TO 1:
        SWAP(array[0], array[i])       // Move the root (max element) to the end
        HEAPIFY_RECURSIVE(array, i, 0) // Restore the heap property for the reduced heap
HEAPIFY_RECURSIVE(array, heapSize, rootIndex):
    largest = rootIndex
    left = 2 * rootIndex + 1
    right = 2 * rootIndex + 2
    // Check if the left child is larger than root
    IF left < heapSize AND array[left] > array[largest]:
        largest = left
    // Check if the right child is larger than the current largest
    IF right < heapSize AND array[right] > array[largest]:
        largest = right
    // If the largest is not root, swap and recursively heapify
    IF largest != rootIndex:
        SWAP(array[rootIndex], array[largest])
        HEAPIFY_RECURSIVE(array, heapSize, largest) // Recursively fix the affected subtree

根据算法，以下代码是使用递归编写的。

示例

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("The array before sorting is: ");
        displayArray(a); 
        Main obj = new Main();
        obj.heapSort(a);
        System.out.println("The array after sorting is: ");
        displayArray(a);
    }
}

编译并运行

输出

The array before sorting is: 
19 4 13 18 10 12 15 
The array after sorting is: 
4 10 12 13 15 18 19

解释

Heapify函数：递归地确保给定索引处的子树满足最大堆属性。如果检测到违反（子节点大于父节点），则会发生交换，并且受影响的子树将递归地进行堆化。

堆排序函数：首先，通过对每个非叶节点调用heapify()函数来构建一个最大堆。然后，将最大元素（根节点）与最后一个元素交换，并减小堆大小。

复杂度分析

时间复杂度为O(n*log (n))，其中n是输入数组中的元素总数。空间复杂度为O(1)。这是因为代码中使用了递归，而递归使用了递归调用堆栈。

使用迭代实现堆排序

算法

HEAP_SORT(array):
    n = length(array)
    // Step 1: Build a max-heap
    FOR i FROM n / 2 - 1 TO 0:
        HEAPIFY_ITERATIVE(array, n, i)
    // Step 2: Extract elements from the heap
    FOR i FROM n - 1 TO 1:
        SWAP(array[0], array[i])       // Move the root (largest element) to the end
        HEAPIFY_ITERATIVE(array, i, 0) // Restore heap property for the reduced heap
HEAPIFY_ITERATIVE(array, heapSize, rootIndex):
    WHILE rootIndex < heapSize:
        largest = rootIndex
        left = 2 * rootIndex + 1
        right = 2 * rootIndex + 2
        // Check if the left child is larger than root
        IF left < heapSize AND array[left] > array[largest]:
            largest = left
        // Check if the right child is larger than the current largest
        IF right < heapSize AND array[right] > array[largest]:
            largest = right
        // If the largest is not root, swap and continue heapifying
        IF largest != rootIndex:
            SWAP(array[rootIndex], array[largest])
            rootIndex = largest          // Update rootIndex to continue heapifying
        ELSE:
            BREAK                       // If heap property is satisfied, exit loop

在以下程序中，我们使用了迭代而不是递归。因此，不会使用额外的空间（递归调用堆栈）。

示例

public class Main { 
// method for building a Max Heap where the value 
// of each parent is always larger 
// than the value of its children 
void createMaxHeap(int a[], int s) 
{ 
	for (int j = 1; j < s; j++) 
	{ 
	// if parent is less than child  
	if (a[j] > a[(j - 1) / 2]) 
	{ 
		int i = j; 
		// swap child and parent till 
		// parent becomes smaller 
		while (a[i] > a[(i - 1) / 2]) 
		{ 
		swapEle(a, i, (i - 1) / 2); 
		i = (i - 1) / 2; 
		} 
	} 
	} 
} 
void heapSort(int a[], int s) 
{ 
	createMaxHeap(a, s); 
	for (int j = s - 1; j > 0; j--) 
	{ 
	// swap the value of the first indexed 
	// with the last indexed 
	swapEle(a, 0, j); 
	// maintaining the property of the max heap  
	// after every swap
	int k = 0, idx; 
	do
	{ 
		idx = (2 * k + 1); 
		// if the left child is smaller than 
		// the right child, point index variable 
		// to the right child 
		if (idx < (j - 1) && a[idx] < a[idx + 1]) 
		idx = idx + 1; 
		// if parent is smaller than child 
		// then swapping parent with child 
		// having higher value 
		if (idx < j && a[k] < a[idx]) 
		swapEle(a, k, idx); 
		k = idx; 
	} while (idx < j); 
	} 
} 
// method for swapping elements located at the indices j and k in the array a[]
void swapEle(int[] a, int j, int k) { 
	int tmp = a[j]; 
	a[j] = a[k]; 
	a[k] = tmp; 
} 
// main method 
public static void main(String args[]) 
{ 
	int a[] = {19, 4, 13, 18, 10, 12, 15}; 
	int s = a.length; 
	Main obj = new Main();
	System.out.print("Unsorted array: "); 
	for (int j = 0; j < s; j++) 
	System.out.print(a[j] + " "); 
	System.out.println();  
	obj.heapSort(a, s); 
	System.out.print("Sorted array: "); 
	for (int j = 0; j < s; j++) 
	System.out.print(a[j] + " "); 
	System.out.println();   
} 
}

编译并运行

输出

Unsorted array: 19 4 13 18 10 12 15 
Sorted array: 4 10 12 13 15 18 19

复杂度分析

在上面的程序中，createMaxHeap()和heapsort()方法需要n*log(n)的时间。因此，总时间复杂度为O(n * log(n))，其中n是输入数组中的元素总数。空间复杂度为O(1)。

堆排序的优点

有效的时间复杂度：在所有情况下，堆排序的时间复杂度均为(n * log(n))，其中n是输入元素的总数。log n因子是由于二叉堆的高度，它确保了即使有大量元素，这种排序的整体性能也很好。

内存使用：堆排序使用最少的空间（可以通过迭代而不是递归编写heapify()方法来实现）。它只需要空间来保存需要排序的项目；除此之外，不需要其他空间。

堆排序的缺点

不稳定：堆排序会重新排列相对顺序。因此，使其不稳定。观察上面代码中元素的交换。

昂贵：与归并排序相比，堆排序中使用的常数的成本更高，尽管两者的时间复杂度均为O(n*log(n)。

效率低下：由于时间复杂度中的常数较高，因此堆排序的效率不高。

堆排序常见问题解答

问）讨论堆排序的两个阶段。

答）堆排序的第一阶段是将输入数组转换为最大堆。堆排序的第二阶段是从堆中删除根元素，然后对剩余元素进行heapfiy()以生成新的最大堆。

问）应该使用哪种排序技术 - 堆排序还是归并排序？

答）如果我们比较时间复杂度，我们会发现归并排序比堆排序在排序元素方面稍快。但是，与堆排序相比，归并排序占用的空间更多。因此，选择哪种排序技术主要取决于需求。

问）为什么堆排序比选择排序更好？

答）与选择排序类似，堆排序会查找最大元素。然而，堆排序查找最大元素的技术比选择排序更好。这种优势是由于在堆排序中使用堆数据结构来查找最大元素。

下一个主题Java中的数字排列

← 上一个下一个 →

Heap Sort in Java

堆排序算法的工作原理

使用递归实现

算法

示例

使用迭代实现堆排序

算法

示例

堆排序的优点

堆排序的缺点

堆排序常见问题解答

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Heap Sort in Java

堆排序算法的工作原理

使用递归实现

算法

示例

使用迭代实现堆排序

算法

示例

堆排序的优点

堆排序的缺点

堆排序常见问题解答

相关帖子

Java JFileChooser

Java 中返回多个值

Java 中的线程安全集合

Order of Execution of Constructors in Java Inheritance

Magic Number in Java

Fermat Number in Java

Java 中的有效正方形问题

Java 社区流程

Java 中 ChoiceFormat applyPattern() 方法及示例

Java 购物账单程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器