Java 堆排序实例(大顶堆、小顶堆)

下面我将为您介绍 Java 堆排序实例(大顶堆、小顶堆)的完整攻略。

1. 堆排序介绍

堆排序是一种树形选择排序方法，它的特点是将数组看成一棵完全二叉树，然后通过建立堆（一种特殊的完全二叉树），逐个取出堆顶元素并重新建堆的过程来进行排序。具体来说，堆排序可以分为两种：大顶堆排序和小顶堆排序。

在大顶堆排序中，堆顶元素最大，从小到大进行排序；在小顶堆排序中，堆顶元素最小，从大到小进行排序。

下面我们将通过示例的方式来讲解 Java 堆排序实例(大顶堆、小顶堆)的攻略。

2. Java 堆排序示例

2.1 大顶堆排序示例

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;
            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 };
        HeapSort ob = new HeapSort();
        ob.sort(arr);
        System.out.println("Sorted array is");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
    }
}

以上代码实现的是大顶堆排序，通过建立大顶堆，每次将堆顶元素（即最大值）取出，然后重新建堆的过程来进行排序。

具体的实现流程如下：

1. 将数组转换成堆，从最后一个非叶子节点开始调整堆的结构，保证所有的子树都符合堆的要求，这个过程叫做 heapify。这一步的过程是从后往前遍历所有的非叶子节点，逐个地将其线性化，即如果有两个子节点，则将它们的值中较大者作为该节点的值，以此类推，直至根节点。

2. 得到堆之后，每次将堆顶元素取出，然后将堆的末尾元素替换到堆顶，再重新调整堆的结构。

3. 重复步骤 2 直到堆为空。

最终输出的结果为：Sorted array is 5 6 7 11 12 13。

2.2 小顶堆排序示例

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;
            heapify(arr, i, 0);
        }
    }

    void heapify(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;
            heapify(arr, n, smallest);
        }
    }

    public static void main(String args[]) {
        int arr[] = { 12, 11, 13, 5, 6, 7 };
        HeapSort ob = new HeapSort();
        ob.sort(arr);
        System.out.println("Sorted array is");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
    }
}

以上代码实现的是小顶堆排序，与大顶堆排序的主要区别是调整堆的过程中要使得所有子树符合小顶堆的要求，即每个节点的值都小于其子节点的值。

最终输出的结果为：Sorted array is 13 12 11 7 6 5。

总结

在本文中，我们介绍了堆排序的概念和实现方法，并通过两个示例分别讲解了大顶堆排序和小顶堆排序的实现方法。堆排序作为一种高效的排序算法，在实际的编程中应用广泛，希望本文的介绍能够帮助读者更好地掌握堆排序的知识。