Java实现堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，它满足堆特性：父节点的值总是大于或等于（最大堆）其子节点的值，或者总是小于或等于（最小堆）其子节点的值。堆排序的平均时间复杂度为 (O(n log n))，空间复杂度为 (O(1))。在这篇博客中，我们将详细探讨如何用Java实现堆排序算法。

简介

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，它满足堆特性：父节点的值总是大于或等于（最大堆）其子节点的值，或者总是小于或等于（最小堆）其子节点的值。堆排序的平均时间复杂度为 (O(n \log n))，空间复杂度为 (O(1))。在这篇博客中，我们将详细探讨如何用Java实现堆排序算法。

目录

1. 基础概念
   • 堆的定义
   • 最大堆和最小堆
   • 堆的操作
2. 使用方法
   • 构建堆
   • 堆排序过程
3. 常见实践
   • 对整数数组进行排序
   • 对自定义对象数组进行排序
4. 最佳实践
   • 优化建议
   • 性能测试
5. 小结
6. 参考资料

基础概念

堆的定义

堆是一种特殊的完全二叉树数据结构，它可以用数组来表示。对于一个数组 arr，如果它表示一个堆，那么对于任意节点 i，它的左子节点的索引为 2*i + 1，右子节点的索引为 2*i + 2，父节点的索引为 (i - 1) / 2。

最大堆和最小堆

• 最大堆：每个父节点的值都大于或等于其子节点的值。在最大堆中，根节点的值是整个堆中的最大值。
• 最小堆：每个父节点的值都小于或等于其子节点的值。在最小堆中，根节点的值是整个堆中的最小值。

堆的操作

• 插入操作：将新元素添加到堆的末尾，然后通过上浮操作（sift up）将其调整到合适的位置，以保持堆的特性。
• 删除操作：通常删除堆顶元素，然后将堆的最后一个元素移动到堆顶，再通过下沉操作（sift down）将其调整到合适的位置。
• 下沉操作（sift down）：从指定节点开始，与它的子节点比较，如果子节点的值更大（对于最大堆）或更小（对于最小堆），则交换位置，并继续向下调整，直到满足堆的特性。
• 上浮操作（sift up）：从指定节点开始，与它的父节点比较，如果节点的值更大（对于最大堆）或更小（对于最小堆），则交换位置，并继续向上调整，直到满足堆的特性。

使用方法

构建堆

构建堆的过程是将一个无序数组转换为一个堆。我们可以从最后一个非叶子节点开始，依次对每个节点进行下沉操作，直到根节点。

public class HeapSort {
    // 下沉操作，将堆中索引为 i 的节点下沉到合适位置
    private static void siftDown(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 temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            // 递归地对受影响的子树进行下沉操作
            siftDown(arr, n, largest);
        }
    }

    // 构建堆
    private static void buildHeap(int[] arr) {
        int n = arr.length;
        // 从最后一个非叶子节点开始，依次对每个节点进行下沉操作
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }
    }
}

堆排序过程

构建好堆后，我们可以通过不断地将堆顶元素（最大值）与堆的最后一个元素交换，然后对剩余的堆进行下沉操作，来完成排序。

public class HeapSort {
    // 堆排序方法
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 构建堆
        buildHeap(arr);

        // 一个一个地从堆顶取出元素
        for (int i = n - 1; i > 0; i--) {
            // 将当前堆顶元素移到数组末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 对剩余的堆进行下沉操作
            siftDown(arr, i, 0);
        }
    }
}

常见实践

对整数数组进行排序

public class Main {
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        HeapSort.heapSort(arr);

        System.out.println("\n排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

对自定义对象数组进行排序

假设我们有一个 Person 类，我们可以根据 Person 的某个属性（如年龄）进行排序。

class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Person other) {
        return this.age - other.age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

public class CustomObjectHeapSort {
    private static void siftDown(Person[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left].compareTo(arr[largest]) > 0)
            largest = left;

        if (right < n && arr[right].compareTo(arr[largest]) > 0)
            largest = right;

        if (largest!= i) {
            Person temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            siftDown(arr, n, largest);
        }
    }

    private static void buildHeap(Person[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }
    }

    public static void heapSort(Person[] arr) {
        int n = arr.length;

        buildHeap(arr);

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

            siftDown(arr, i, 0);
        }
    }

    public static void main(String[] args) {
        Person[] people = {
                new Person("Alice", 25),
                new Person("Bob", 20),
                new Person("Charlie", 30)
        };

        System.out.println("排序前的数组:");
        for (Person person : people) {
            System.out.println(person);
        }

        heapSort(people);

        System.out.println("排序后的数组:");
        for (Person person : people) {
            System.out.println(person);
        }
    }
}

最佳实践

优化建议

• 减少交换次数：可以使用一个临时变量来存储当前要调整的节点的值，而不是每次都进行完整的交换操作，这样可以减少一些不必要的内存访问。
• 使用不同的堆操作实现：对于一些特殊情况，可以考虑使用不同的堆操作实现，如使用索引堆（Index Heap），它可以在不改变原始数组顺序的情况下进行堆操作，适用于一些需要保留原始数据索引的场景。

性能测试

可以使用Java的 System.currentTimeMillis() 方法来测试堆排序算法的性能。例如：

public class PerformanceTest {
    public static void main(String[] args) {
        int[] largeArray = new int[1000000];
        for (int i = 0; i < largeArray.length; i++) {
            largeArray[i] = (int) (Math.random() * 1000000);
        }

        long startTime = System.currentTimeMillis();
        HeapSort.heapSort(largeArray);
        long endTime = System.currentTimeMillis();

        System.out.println("堆排序耗时: " + (endTime - startTime) + " 毫秒");
    }
}

通过性能测试，可以对比不同优化策略下堆排序算法的性能表现，从而选择最适合的实现方式。

小结

堆排序是一种高效的排序算法，它利用堆这种数据结构的特性，在 (O(n \log n)) 的时间复杂度内完成排序。通过理解堆的基本概念、操作方法以及在Java中的实现方式，我们可以灵活地应用堆排序算法解决各种排序问题。同时，通过优化和性能测试，我们可以进一步提高算法的效率和适用性。希望这篇博客能帮助你更好地理解和使用Java实现堆排序算法。

参考资料

• 《算法导论》（Introduction to Algorithms）
• 维基百科 - 堆排序
• Oracle Java 文档