堆排序 (Heap Sort)

算法原理

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

算法步骤

1. 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区
2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn)
3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆
4. 重复步骤2-3，直到有序区的元素个数为n-1

代码实现

public class HeapSort {
    public static void heapSort(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);
        }
    }
    
    // 调整堆以维持最大堆性质
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;  // 初始化最大为根节点
        int left = 2 * i + 1;   // 左子节点
        int right = 2 * i + 2;  // 右子节点
        
        // 如果左子节点存在且大于根节点
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        // 如果右子节点存在且大于当前最大节点
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        // 如果最大节点不是根节点
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            
            // 递归调整受影响的子树
            heapify(arr, n, largest);
        }
    }

    // 测试方法
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前:");
        printArray(arr);

        heapSort(arr);

        System.out.println("排序后:");
        printArray(arr);
    }

    static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

应用场景

• 优先队列：堆是实现优先队列的最佳数据结构
• 寻找第K大元素：可以使用堆排序的思想在O(n)时间内找到第K大元素
• 内存受限环境：由于是原地排序，适用于内存受限的环境
• 需要稳定时间复杂度的场景：堆排序的时间复杂度稳定为O(n log n)

优缺点