经典算法：堆排序算法

正经程序员 2023-01-25 19 1

前言

堆排序是指用堆这种数据结构所设计的排序算法，堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或大于）它的父节点。

堆排序是一种就地、基于比较的排序算法，可以被认为是一种改进的选择排序，因为它将输入划分为已排序和未排序的区域。它通过提取最大/最小元素并将其移动到已排序区域来迭代地缩小未排序区域。

改进包括使用堆数据结构而不是线性时间搜索来找到最大值。堆排序不会产生稳定的排序，这意味着堆排序不会保留已排序输出中相等元素的输入顺序。通常比其他算法慢，比如快速排序、合并排序等。

堆排序算法可以分为两部分：

1.第一步，根据输入结构构建一个堆，可以在O(n)时间内做到这一点。 2.通过重复从堆中删除最大/最小元素并将其插入到数组中来创建排序数组，每次删除后都会更新堆以维护堆属性。一旦从堆中删除所有元素，就会得到一个排序数组。这是在O(n.log(n))时间内完成的，因为我们需要弹出n元素，其中每次删除都涉及固定数量的工作，并且单个堆积操作需要O(log(n))时间。

Java示例

public class HeapSort {
    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;
 
            // 在减少的堆上调用 max heapify
            heapify(arr, i, 0);
        }
    }
 
    // 对以节点i为根的子树进行堆积，节点i是arr[]中的索引，n是堆积的大小
    void heapify(int arr[], int n, int i)
    {
        int largest = i; // 初始化最大为根
        int l = 2 * i   1; // left = 2*i   1
        int r = 2 * i   2; // right = 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);
        }
    }
 
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n;   i)
        System.out.print(arr[i]   " ");
        System.out.println();
    }
 
    public static void main(String args[])
    {
        int arr[] = { 12, 11, 13, 5, 6, 7 };
        int n = arr.length;
 
        HeapSort ob = new HeapSort();
        ob.sort(arr);
 
        System.out.println("排序后的数组为：");
        printArray(arr);
    }
}

输出：

排序后的数组为：5 6 7 11 12 13