数据结构第22节堆排序优化

作者：小惠珠哦 | 2024-07-14 15:42:12

踩

数据结构第22节堆排序优化

堆排序是一种基于比较的排序算法，其核心是使用一种叫做“堆”的数据结构。堆通常是一个完全二叉树的数组表示，在数组中可以快速找到最大值或最小值。堆排序可以分为两种类型：最大堆和最小堆。

在最大堆中，父节点的键始终大于或等于任何子节点的键。在最小堆中，情况则相反，父节点的键始终小于或等于任何子节点的键。堆排序通常使用最大堆进行降序排序，或者使用最小堆进行升序排序。

以下是使用Java实现堆排序的基本步骤：

构建最大堆：
- 将输入数组视为一个完全二叉树的数组表示。
- 从最后一个非叶子节点开始（即array.length / 2 - 1），对每个节点应用下沉操作，以确保其满足最大堆的性质。
排序：
- 将堆顶元素（最大值）与堆末尾的元素交换，减少堆的大小，并将新的堆顶元素下沉，使其再次满足最大堆的性质。
- 重复此过程，直到堆的大小减少到1。

下面是一个具体的Java代码示例来实现堆排序：

public class HeapSort {
    public static void heapSort(int[] array) {
        // Build heap (rearrange array)
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            heapify(array, array.length, i);
        }

        // One by one extract an element from heap
        for (int i = array.length - 1; i > 0; i--) {
            // Move current root to end
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            // call max heapify on the reduced heap
            heapify(array, i, 0);
        }
    }

    // To heapify a subtree rooted with node i which is an index in array[]
    private static void heapify(int[] array, int heapSize, int i) {
        int largest = i; // Initialize largest as root
        int leftChild = 2 * i + 1; // left child
        int rightChild = 2 * i + 2; // right child

        // If left child is larger than root
        if (leftChild < heapSize && array[leftChild] > array[largest]) {
            largest = leftChild;
        }

        // If right child is larger than largest so far
        if (rightChild < heapSize && array[rightChild] > array[largest]) {
            largest = rightChild;
        }

        // If largest is not root
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(array, heapSize, largest);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

在这个例子中，heapSort函数首先通过调用heapify函数建立一个最大堆，然后将堆顶元素与堆的最后一个元素交换，减少堆的大小，并重新调整剩余元素以保持最大堆的性质。这样重复直到整个数组排序完成。

为了进一步优化堆排序的代码，我们可以考虑以下几点：

内联小函数：如果heapify函数很小且频繁调用，可以考虑将其内联到heapSort函数中，以减少函数调用的开销。
减少数组访问：在heapify函数中，多次访问array中的元素可能会导致缓存未命中，从而影响性能。我们可以通过缓存一些频繁访问的值来减少这种影响。
边界条件检查：确保在循环中检查边界条件，避免不必要的计算。
使用循环展开：对于某些循环，使用循环展开可以减少循环控制结构的开销。
尾递归优化：如果使用了递归的heapify，可以尝试将其转换为迭代版本，因为JVM可能不支持尾递归优化。

下面是一个经过微调的堆排序实现，其中heapify函数被内联并进行了数组访问优化：

public class HeapSortOptimized {
    public static void heapSort(int[] array) {
        int n = array.length;
        
        // Build heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            int largest = i;
            int leftChild = 2 * i + 1;
            int rightChild = 2 * i + 2;
            
            if (leftChild < n && array[leftChild] > array[largest]) {
                largest = leftChild;
            }
            
            if (rightChild < n && array[rightChild] > array[largest]) {
                largest = rightChild;
            }
            
            if (largest != i) {
                int temp = array[i];
                array[i] = array[largest];
                array[largest] = temp;
                
                // Recursively heapify the affected sub-tree
                i = largest;
                leftChild = 2 * i + 1;
                rightChild = 2 * i + 2;
                
                while (leftChild < n) {
                    largest = i;
                    if (array[leftChild] > array[largest]) {
                        largest = leftChild;
                    }
                    
                    if (rightChild < n && array[rightChild] > array[largest]) {
                        largest = rightChild;
                    }
                    
                    if (largest == i) {
                        break;
                    }
                    
                    temp = array[i];
                    array[i] = array[largest];
                    array[largest] = temp;
                    
                    i = largest;
                    leftChild = 2 * i + 1;
                    rightChild = 2 * i + 2;
                }
            }
        }
        
        // Extract elements one by one
        for (int i = n - 1; i > 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            
            int j = 0;
            int leftChild = 1;
            int rightChild = 2;
            
            while (leftChild < i) {
                int largest = j;
                if (array[leftChild] > array[largest]) {
                    largest = leftChild;
                }
                
                if (rightChild < i && array[rightChild] > array[largest]) {
                    largest = rightChild;
                }
                
                if (largest == j) {
                    break;
                }
                
                temp = array[j];
                array[j] = array[largest];
                array[largest] = temp;
                
                j = largest;
                leftChild = 2 * j + 1;
                rightChild = 2 * j + 2;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

这个优化版本中，heapify逻辑被直接整合到了heapSort函数中，并且在每次交换后都检查是否需要继续下沉，以避免不必要的额外工作。此外，数组元素的频繁访问被优化，减少了不必要的内存读取。但是，值得注意的是，过度优化可能会影响代码的可读性和维护性，因此在实际开发中需要权衡利弊。

堆排序的过程可以分为两个主要阶段：构建最大堆和排序。我将以一个简单的示例数组 [4, 10, 3, 5, 1] 来逐步说明堆排序的过程，并使用表格形式展示每一步的变化。

第一阶段：构建最大堆

初始状态:

| Index | Value |
|-------|-------|
|   0   |   4   |
|   1   |  10   |
|   2   |   3   |
|   3   |   5   |
|   4   |   1   |
1
2
3
4
5
6
7

从最后一个非叶节点开始下沉:
- 节点 1 (值 10) 是最后一个非叶节点。
- 节点 1 已经是最大堆的一部分，无需调整。
节点 0 下沉:
- 节点 0 (值 4) 有子节点 1 (值 10) 和 2 (值 3)，其中最大的是子节点 1。
- 交换节点 0 和节点 1 的值。
```
| Index | Value |
|-------|-------|
|   0   |  10   |
|   1   |   4   |
|   2   |   3   |
|   3   |   5   |
|   4   |   1   |
1
2
3
4
5
6
7
```
- 节点 0 现在是值 10，它没有子节点比它大，所以不需要进一步调整。

现在，我们有一个最大堆:

| Index | Value |
|-------|-------|
|   0   |  10   |
|   1   |   4   |
|   2   |   3   |
|   3   |   5   |
|   4   |   1   |
1
2
3
4
5
6
7

第二阶段：排序

交换堆顶元素与最后一个元素:

交换节点 0 (值 10) 和节点 4 (值 1)。

| Index | Value |
|-------|-------|
|   0   |   1   |
|   1   |   4   |
|   2   |   3   |
|   3   |   5   |
|   4   |  10   |
1
2
3
4
5
6
7

减少堆的大小，不再考虑索引 4。

调整堆:
- 节点 0 (值 1) 需要下沉。
- 交换节点 0 和节点 3 (值 5)。
```
| Index | Value |
|-------|-------|
|   0   |   5   |
|   1   |   4   |
|   2   |   3   |
|   3   |   1   |
|   4   |  10   |
1
2
3
4
5
6
7
```
- 节点 0 现在是值 5，它没有子节点比它大，所以不需要进一步调整。
再次交换堆顶元素与最后一个元素:
- 交换节点 0 (值 5) 和节点 3 (值 1)。
```
| Index | Value |
|-------|-------|
|   0   |   1   |
|   1   |   4   |
|   2   |   3   |
|   3   |   5   |
|   4   |  10   |
1
2
3
4
5
6
7
```
- 减少堆的大小，不再考虑索引 3。
调整堆:
- 节点 0 (值 1) 需要下沉。
- 由于节点 0 没有子节点，不需要进一步调整。

重复以上步骤，直到堆的大小减至 1。

最终排序结果:

| Index | Value |
|-------|-------|
|   0   |   1   |
|   1   |   3   |
|   2   |   4   |
|   3   |   5   |
|   4   |  10   |
1
2
3
4
5
6
7

这就是堆排序的完整过程，通过构建最大堆和不断交换并调整堆，最后得到一个有序的数组。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小惠珠哦/article/detail/825366

数据结构第22节 堆排序优化

第一阶段：构建最大堆

第二阶段：排序

数据结构第22节堆排序优化