java实现堆排序算法

原创admin 分类：热门问答 2024-05-24 23:36:03 0

java实现堆排序算法
在计算机科学的世界里，排序算法是数据结构和算法领域中一个永恒的话题。我作为一名程序员，经常需要处理各种数据排序问题。堆排序，作为一种高效的排序算法，以其独特的优势在众多排序算法中脱颖而出。堆排序是一种基于二叉堆数据结构的排序方法，它通过构建最大堆或最小堆来实现对数据的排序。

定义与目的

堆排序的基本思想是将待排序的数组构建成一个堆结构，然后通过交换堆顶元素与最后一个元素，逐步将最大（或最小）元素移出堆，实现排序。堆排序的目的在于提供一个时间复杂度为O(nlogn)的稳定排序算法，适用于大数据量的排序任务。

核心类与方法

在Java中，堆排序通常不需要单独的类来实现，而是通过数组和一些辅助方法来完成。核心方法包括：

buildMaxHeap：构建最大堆，确保每个父节点的值都大于或等于其子节点的值。
heapify：调整堆，确保堆的性质在删除或插入元素后得以维持。
heapSort：执行堆排序，通过不断调整堆并移除最大元素来对数组进行排序。

使用场景

堆排序适用于需要对大数据集进行排序的场景，尤其是在内存受限的情况下，由于其空间复杂度为O(1)，即不需要额外的存储空间。此外，堆排序在优先队列的实现中也非常常见。

代码案例

以下是使用Java实现堆排序的两个详细代码案例：

案例一：基本的堆排序实现

public class HeapSort {
    void sort(int arr[]) {
        int n = arr.length;

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // One by one extract an element from heap
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    void heapify(int arr[], int n, int i) {
        int largest = i; // Initialize largest as root
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

    // Driver code
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        HeapSort hs = new HeapSort();
        hs.sort(arr);

        System.out.println("Sorted array is");
        for (int i : arr)
            System.out.print(i + " ");
    }
}

案例二：使用Java内置的PriorityQueue实现堆排序

import java.util.PriorityQueue;

public class HeapSortWithPriorityQueue {
    void sort(int arr[]) {
        PriorityQueue<Integer, Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            pq.offer(new Integer(arr[i]), i); // offer with index
        }

        // Extract elements from PriorityQueue
        for (int i = 0; i < arr.length; i++) {
            arr[i] = pq.poll().intValue();
        }
    }

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        HeapSortWithPriorityQueue hs = new HeapSortWithPriorityQueue();
        hs.sort(arr);

        System.out.println("Sorted array is");
        for (int i : arr)
            System.out.print(i + " ");
    }
}

对比表格

特性	基本堆排序	使用PriorityQueue的堆排序
空间复杂度	O(1)	O(n)
时间复杂度	O(nlogn)	O(nlogn)
实现复杂度	较高	较低
适用场景	大数据集排序	需要额外索引的场景

问题	回答
堆排序是稳定的排序算法吗？	不是，堆排序不是稳定的排序算法。
堆排序的空间复杂度是多少？	堆排序的空间复杂度为O(1)，因为它是原地排序算法。
如何构建最大堆？	从最后一个非叶子节点开始，向上调整，确保每个节点都满足最大堆的性质。
PriorityQueue如何实现堆排序？	PriorityQueue内部维护了一个最小堆，通过添加元素和索引，然后在排序时根据索引顺序取出元素，实现排序。