java堆排序工具类

在编程的世界里，排序算法是基础且重要的一环，它影响着数据的组织和检索效率。堆排序作为一种高效的比较类排序算法，以其独特的性能特点在众多排序算法中占有一席之地。本文将从堆排序的定义出发，详细解释其工作原理，并通过两个代码案例，展示如何在Java中实现堆排序工具类。

1. 堆排序定义与重要性

堆排序（Heap Sort）是一种基于比较的排序算法，它利用了二叉堆的数据结构来实现排序。堆是一种特殊的完全二叉树，可以看作是一个数组，其中每个节点都满足堆性质：即对于任意节点i，其值都不大于其子节点的值（最大堆）或不小于其子节点的值（最小堆）。堆排序的核心在于将待排序数组构建成一个堆，然后通过交换堆顶元素与最后一个元素，逐步将最大（或最小）元素移动到数组的末尾，直到堆中元素全部被移除。

2. 堆排序与其他排序算法的对比

堆排序与快速排序、归并排序等其他常见排序算法相比，有其独的优势和局限性。以下是堆排序与其他两种排序算法的对比表格：

3. 核心类与方法

在Java中实现堆排序，核心类通常是一个堆数据结构的实现，而核心方法则包括构建堆（buildHeap）、堆调整（heapify）以及执行排序（heapSort）。以下是这些核心方法的简要说明：

• 构建堆：将无序的数组转换为一个最大堆。
• 堆调整：确保堆的性质在数组中得以维持。
• 执行排序：通过交换堆顶元素与末尾元素，并重新调整堆，逐步完成排序。

4. 使用场景

堆排序适用于那些对内存使用有限制的场景，因为它是一种原地排序算法，不需要额外的存储空间。此外，堆排序的时间复杂度稳定，对于大数据量的排序任务，它能够提供可预测的性能。

5. 代码案例

以下是两个简单的Java堆排序工具类的代码案例：

案例一：使用数组实现的最大堆排序

public class HeapSortExample1 {
    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 static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        HeapSortExample1 heapSort = new HeapSortExample1();
        heapSort.sort(arr);

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

案例二：使用自定义堆类实现的堆排序

public class HeapSortExample2 {
    public void sort(Heap<Integer> maxHeap) {
        int n = maxHeap.size();

        // 执行堆排序
        for (int i = n - 1; i > 0; i--) {
            // 交换堆顶元素和末尾元素
            int temp = maxHeap.peek();
            maxHeap.replaceWithLast(i);
            maxHeap.heapify(i);
        }
    }

    public static void main(String[] args) {
        Heap<Integer> maxHeap = new Heap<>();
        maxHeap.add(12);
        maxHeap.add(11);
        maxHeap.add(13);
        maxHeap.add(5);
        maxHeap.add(6);
        maxHeap.add(7);

        HeapSortExample2 heapSort = new HeapSortExample2();
        heapSort.sort(maxHeap);

        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " ");
        }
    }
}

class Heap<T extends Comparable<T>> {
    private final ArrayList<T> heap;

    public Heap() {
        this.heap = new ArrayList<>();
    }

    public void add(T value) {
        heap.add(value);
        siftUp(heap.size() - 1);
    }

    public T peek() {
        return heap.get(0);
    }

    public T poll() {
        T item = heap.get(0);
        replaceWithLast(0);
        heapify(0);
        return item;
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }

    private void replaceWithLast(int i) {
        T value = heap.get(i);
        heap.set(i, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);
        siftDown(i, value);
    }

    private void siftUp(int index) {
        T value = heap.get(index);
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (value.compareTo(heap.get(parent)) < 0) {
                heap.set(index, heap.get(parent));
                index = parent;
            } else {
                break;
            }
        }
        heap.set(index, value);
    }

    private void siftDown(int index, T value) {
        while (index < heap.size() / 2) {
            int left = 2 * index + 1;
            int right = left + 1;
            int largestIndex = index;

            if (heap.get(left).compareTo(heap.get(largestIndex)) > 0) {
                largestIndex = left;
            }

            if (right < heap.size() && heap.get(right).compareTo(heap.get(largestIndex)) > 0) {
                largestIndex = right;
            }

            if (largestIndex != index) {
                heap.set(index, heap.get(largestIndex));
                index = largestIndex;
            } else {
                break;
            }
        }
        heap.set(index, value);
    }

    private void heapify(int index) {
        T value = heap.get(index);
        siftDown(index, value);
    }

    private int size() {
        return heap.size();
    }
}

6. 相关知识点补充

以下是一些与堆排序相关的知识点，通过表格形式进行展示：

通过上述内容，我们对堆排序有了全面的了解，包括其定义、与其他排序算法的对比、核心类与方法、使用场景以及两个具体的代码案例。希望这些信息能够帮助你更好地理解和应用堆排序算法。