堆排序（简单易懂，适合初学者）

╰+攻爆jí腚メ 2023-09-27 17:26 133阅读 0赞

### 什么是堆 ###

堆是一种特殊的树形结构，叫做完全二叉树。它有两种类型：大顶堆和小顶堆。在大顶堆中，每个父节点都比它的子节点大；而在小顶堆中，每个父节点都比它的子节点小。堆排序就是利用这种结构设计的一种排序方法。

### 堆的分类 ###

大顶堆:对于每一个节点来说，它的值都大于他的左孩子的值和右孩子节点的值。  
![大顶堆][c6e4dae44d41474ab04f201f15454d30.png]  
小顶堆：对于每一个节点来说，它的值都小于他的左孩子的值和右孩子节点的值。

![在这里插入图片描述][fdd8979d88114a1fbaf81ba2f80b78fc.png]

**如果将以上两种堆变成数组，如下图所示:**

**大顶堆：**

![在这里插入图片描述][4953abc823ff434b8be7823d816ceb70.png]

**小顶堆**

![在这里插入图片描述][254c11affcc743a98ffb960a0100b1df.png]

### 排序思想 ###

首先，把要排序的数组变成一个大顶堆，这样最大的数就在堆的顶部。

接着，把堆顶的数和数组的最后一个数交换。现在，最大的数已经在数组的末尾，剩下的数组元素个数变为 n-1。

对剩下的 n-1 个数再次构建大顶堆，然后把新堆顶的数和 n-1 位置的数交换。不断重复这个过程，直到得到一个升序排列的数组。

注意：要得到升序排列的数组，用大顶堆；要得到降序排列的数组，用小顶堆（默认情况下，我们使用升序排序）。

### 如何构造堆 ###

![在这里插入图片描述][d96d06447b3d4875958e2feddc56dc3d.png]

首先我们给定一个无序的序列，将其看做一个堆结构，一个没有规则的二叉树，将序列里的值按照从上往下，从左到右依次填充到二叉树中。

![在这里插入图片描述][7c5312ea7e2b4fd6ad33f8fb9adafd45.png]

在一个完全二叉树中，当所有非叶子节点都有两个子节点时，每一层的节点数是上一层的两倍。根节点有1个，所以最后一层的节点数等于之前所有层节点总数加1。因此，我们可以找到最后一层的第一个节点的索引，即节点总数除以2（根节点索引为0）。这就是第一个叶子节点的索引。那么第一个非叶子节点的索引就是最后一个叶子节点的索引减1。

对于不完全填满的二叉树，这种计算方法仍然适用。当我们按照从上到下、从左到右的顺序填充二叉树时，第一个叶子节点的索引一定是序列长度除以2。所以，最后一个非叶子节点的索引是 arr.len / 2 - 1。**例如，对于数组长度为5的情况，最后一个非叶子节点的索引为 5 / 2 - 1 = 1，即节点值为 6 的节点。**

那么如何构建大顶堆呢？我们找到了最后一个非叶子节点，即节点值为 6 的节点。**我们需要比较它的左右子节点中值最大的那个，如果这个最大值比当前节点大，就交换它们的位置。**

在这个例子中，节点值为 6 的节点有两个子节点，分别为 5 和 9。9 大于 6，所以我们交换 6 和 9 的位置。这样，我们就在局部构建了一个大顶堆。

![在这里插入图片描述][52575d50617049a0aed4951cf31d2638.png]  
找到下一个非叶子节点4，用它和它的左右子节点进行比较，4大于3，而4小于9，交换4和9位置

![在这里插入图片描述][6e6b7c4b7db848c9bfde7d4bb96edfde.png]  
此时发现4小于5和6这两个子节点，我们需要进行调整，左右节点5和6中，6大于5且6大于父节点4，因此交换4和6的位置  
![在这里插入图片描述][f3224d3b655946f0b6daf2a48e6608d7.png]  
**现在我们已经构建了一个大顶堆，接下来进行排序。**

首先，将堆顶元素（假设为9）与数组末尾元素（假设为4）交换位置。此时，数组末尾的数字是最大值。然后，**排除已经确定的最大元素，将剩下的元素重新构建成一个大顶堆。**

**以下是第一次交换的示意图：**

![在这里插入图片描述][dcefb840d8ff42408b21bf9e00a30243.png]  
**以下是第二次交换的示意图**

![在这里插入图片描述][a3ba101715834646b435f80991d285de.png]  
**最终的排序结果为：**

![在这里插入图片描述][c41c03b8c2c6406ab63b074e1c924127.png]  
由此，我们可以归纳出堆排序算法的步骤：

将无序数组构建成一个大顶堆（或小顶堆，取决于所需排序顺序）。

循环地将堆顶元素移动到数组尾部，并调整堆结构，生成新的堆顶。

当我们将一个最大堆的堆顶元素移动到数组末尾（实际上是交换堆顶和末尾元素的位置），堆会自我调整，使得次大的元素成为新的堆顶。

就像前面的例子，当我们移走值为9的堆顶元素后，堆会调整使值为6的元素成为新的堆顶；当我们再次移走值为6的堆顶元素，堆会调整使值为5的元素成为新的堆顶，以此类推。

由于二叉堆的这个特性，每次移动堆顶元素并调整堆结构后，新的堆顶都是仅次于前一个堆顶的元素。因此，我们只需要不断地移动堆顶元素并调整堆结构，最终得到的数组就会是一个有序数组。

### 示例代码： ###

public class HeapSort {
        
        public static void main(String[] args) {
        
            int[] arr = {
        12, 11, 13, 5, 6, 7};
            heapSort(arr);
            System.out.println("排序后的数组：");
            for (int i : arr) {
        
                System.out.print(i + " ");
            }
        }
    
        public 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 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);
            }
        }
    }

[c6e4dae44d41474ab04f201f15454d30.png]: https://img-blog.csdnimg.cn/c6e4dae44d41474ab04f201f15454d30.png
[fdd8979d88114a1fbaf81ba2f80b78fc.png]: https://img-blog.csdnimg.cn/fdd8979d88114a1fbaf81ba2f80b78fc.png
[4953abc823ff434b8be7823d816ceb70.png]: https://img-blog.csdnimg.cn/4953abc823ff434b8be7823d816ceb70.png
[254c11affcc743a98ffb960a0100b1df.png]: https://img-blog.csdnimg.cn/254c11affcc743a98ffb960a0100b1df.png
[d96d06447b3d4875958e2feddc56dc3d.png]: https://img-blog.csdnimg.cn/d96d06447b3d4875958e2feddc56dc3d.png
[7c5312ea7e2b4fd6ad33f8fb9adafd45.png]: https://img-blog.csdnimg.cn/7c5312ea7e2b4fd6ad33f8fb9adafd45.png
[52575d50617049a0aed4951cf31d2638.png]: https://img-blog.csdnimg.cn/52575d50617049a0aed4951cf31d2638.png
[6e6b7c4b7db848c9bfde7d4bb96edfde.png]: https://img-blog.csdnimg.cn/6e6b7c4b7db848c9bfde7d4bb96edfde.png
[f3224d3b655946f0b6daf2a48e6608d7.png]: https://img-blog.csdnimg.cn/f3224d3b655946f0b6daf2a48e6608d7.png
[dcefb840d8ff42408b21bf9e00a30243.png]: https://img-blog.csdnimg.cn/dcefb840d8ff42408b21bf9e00a30243.png
[a3ba101715834646b435f80991d285de.png]: https://img-blog.csdnimg.cn/a3ba101715834646b435f80991d285de.png
[c41c03b8c2c6406ab63b074e1c924127.png]: https://img-blog.csdnimg.cn/c41c03b8c2c6406ab63b074e1c924127.png