java 堆排序实现

原创admin 分类：热门问答 2024-05-18 14:51:09 0

java 堆排序实现
在计算机科学中，排序算法是处理数据集合的基石之一。我经常思考如何将数据以一种有序的方式展示，而堆排序（Heap Sort）正是实现这一目标的有效工具之一。堆排序是一种比较和交换元素的排序算法，它利用了二叉堆（Binary Heap）的数据结构。与快速排序和归并排序相比，堆排序在最坏情况下的时间复杂度为O(n log n)，这使得它在某些应用场景下显得尤为有用。

定义与目的

堆排序基于堆的概念，堆是一种特殊的完全二叉树，它满足两个特性：结构性（Complete Tree）和堆序性（Heap Property）。结构性意味着除了最后一层外，其他层的节点都是满的，并且最后一层的节点尽可能地集中在左侧。堆序性则是指每个节点的值都满足一定的顺序性，可以是最大堆或最小堆。

核心类与方法

堆排序的核心在于构建堆和调整堆两个操作。构建堆（Build Heap）是将一个无序数转换成堆结构的过程。调整堆（Heapify）则是在删除或插入节点后，重新调整堆以保持堆的性质。堆排序算法包括两个主要的函数：

buildHeap：将无序数组构建成最大堆或最小堆。
heapSort：使用构建的堆来排序数组。

使用场景

堆排序适用于那些需要稳定排序算法的场景，因为它是稳定的排序算法。此外，当数据量较大且内存使用需要优化时，堆排序也是一个不错的选择，因为它是原地排序算法，不需要额外的存储空间。

代码案例

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

案例一：最大堆排序

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

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

        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    void heapify(int arr[], int n, int i) {
        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;

        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }
}

案例二：最小堆排序

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

        for (int i = n / 2 - 1; i >= 0; i--)
            heapifyMin(arr, n, i);

        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapifyMin(arr, i, 0);
        }
    }

    void heapifyMin(int arr[], int n, int i) {
        int smallest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && arr[l] < arr[smallest])
            smallest = l;

        if (r < n && arr[r] < arr[smallest])
            smallest = r;

        if (smallest != i) {
            int swap = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = swap;

            heapifyMin(arr, n, smallest);
        }
    }
}

对比表格

属性	堆排序（最大堆）	堆排序（最小堆）
构建堆方法	`buildHeap`	`buildHeap`
调整堆方法	`heapify`	`heapifyMin`
排序方式	从最大元素开始	从最小元素开始
适用场景	大数据量排序	大数据量排序

问题	回答
堆排序的时间复杂度是多少？	最坏、平均、最佳情况下都是O(n log n)。
堆排序是稳定的排序算法吗？	是的，堆排序是稳定的排序算法。
堆排序需要额外的存储空间吗？	不需要，堆排序是原地排序算法。
堆排序适用于哪些场景？	适用于需要稳定排序且数据量较大的场景。