排序-堆排序

    完全二叉树是叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。

    堆是有如下特点的完全二叉树

  • 根节点的值>=子节点的值，即大顶堆

  • 根节点的值<=子节点的值，即小顶堆

    

构建大顶堆

  • 从0开始，将每一个数字依次插入，一边插入一边调整堆的结构，使之满足大顶堆的要求

  • 将整个数列试作完全二叉树，自底向上调整树的结构，使之满足大顶堆的要求

建堆与堆化

  • 建堆即构建堆

  • 堆化是从当前位置开始调整数组使之满足堆的特征

堆排序的过程

  • 构建大顶堆

  • 取出堆顶元素

  • 调整剩余数字使之符合大顶堆特点

  • 再次取出堆顶元素

  • 循环往复

完全二叉树的性质(根节点下标为0)

  • 下标i的左子节点下标：2 * i + 1

  • 下表i的右子节点下标：左下标+1

  • 最后一个非叶子节点下标：n/2-1

堆排序的复杂度分析

    堆排序的时间复杂度为O(n log n)，堆排序的空间复杂度为 O(1)。

    时间复杂度分析由建堆和堆化两个，其中建堆的时间复杂度是O(n)，堆化的时间复杂度是O(n log n)

堆排序代码
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

public void testHeapSort() {
    int[] arr = new int[]{6, 2, 1, 3, 5, 4};
    buildMaxHeap(arr);

    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        maxHeapify(arr, 0, i);
    }
    
}

/**
 * 构建大顶堆
 * <p>
 * 我要成为亿万富翁
 * 我要财务自由
 */
private void buildMaxHeap(int[] arr) {
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, i, arr.length);
    }
}

/**
 * 堆化
 * <p>
 * 我要成为亿万富翁
 * 我要财务自由
 *
 * @param arr
 * @param i
 * @param size
 */
private void maxHeapify(int[] arr, int i, int size) {
    int left = 2 * i + 1;
    int right = left + 1;

    int maxValue = i;
    if (left < size && arr[left] > arr[maxValue]) {
        maxValue = left;
    }
    if (right < size && arr[right] > arr[maxValue]) {
        maxValue = right;
    }

    if (maxValue != i) {
        swap(arr, i, maxValue);
        maxHeapify(arr, maxValue, size);
    }
}

/**
 * 交换数组arr 下标 i j  的数据
 * <p>
 * 我要成为亿万富翁
 * 我要财务自由
 *
 * @param arr
 * @param i
 * @param j
 */
private void swap(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[j] ^ arr[i];
    arr[i] = arr[i] ^ arr[j];
}