背景

 过完年就要春招了，数据结构和算法是面试中的重要内容，尤其是数据结构。趁着最近已经基本没课，时间比较多，学习一些比较常见的算法。今天刚学会堆排序，写篇博客记录一下。


描述

什么是堆？

  学习堆排序，那我们首先得知道，什么是堆。堆其实就是一棵完全二叉树，分为两种：

  1. 大根堆：每个根节点的值都比它左右节点的值要大；
  2. 小根堆：每个根节点的值都比它左右节点的值要小；

  若用数组存储一个完全二叉树，那根节点的索引与左右子节点的索引满足以下条件：

  1. 左子节点索引 = 根节点索引 × 2 + 1；
  2. 右子节点索引 = 根节点索引 × 2 + 2；

如何建立堆

  以大根堆为例，我们知道，在大根堆中，每一个根节点的值，都大于它左右节点的值，而建堆的过程，其实就是调整这棵完全二叉树中节点的位置。我们从最后一个根节点开始，调整节点的位置，若当前根节点的值小于其子节点的值，则将值最大的子节点与根节点交换，交换过程实际上就是交换数组中的两个位置的值，通过上面说的根节点与子节点索引的关系；此过程结束，继续上一个根节点，重复此过程，直到整个堆的根节点置换完毕，则堆建立完毕。

  假设堆中一共有n个节点，那最后一个根节点的下标就是n/2-1，因为在完全二叉树中，共有n/2个子节点。所以我们可以知道，在存储的数组中，0 ~ n/2-1都是非叶子节点，后面的都是叶子节点，所以建堆就是从n/2-1到0这些非叶子结点以此进行。

如何进行堆排序

  我们建立好大根堆后，堆顶元素就是所有数中最大的了，此时我们将堆顶与数组中的最后一位置交换，然后再将1 ~ n-1个元素建立成大根堆，并将堆顶与数组中第n-1个位置交换，以此类推，每次都能得到剩余值中最大的值，放到最后。进行n-1次，则就得到了一个有序的数组了。


代码

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
89
90
91
92
93
import java.util.Arrays;

/**
 * Java实现堆排序
 */
@SuppressWarnings("all")
public class HeapSort {

    public static void main(String[] args) {
        int[] a = {4,1,2,5,3,8,6};
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }

    /**
     * 堆排序
     * @param arr
     * @return
     */
    public static int[] heapSort(int[] arr) {
        int len = arr.length;

        // 建立初始大根堆
        buildMaxHeap(arr, len);

        // 依次将堆顶的最大值放到数组的最后，并重新建堆
        for (int i = len - 1; i > 0; --i) {
            swap(arr, 0, i);
            len--;
            heapity(arr, 0, len);
        }
        return arr;
    }

    /**
     * 建立初始大根堆
     * @param arr
     * @param len
     */
    private static void buildMaxHeap(int[] arr, int len) {
        // 遍历所有非叶子节点，进行建堆操作
        // 在完全二叉树中，共n个节点，则0 ~ (n/2)-1为非叶子节点
        for (int i = len / 2 - 1; i >= 0; --i) {
            heapity(arr, i, len);
        }
    }

    /**
     * 建立大根堆的过程中，调整节点位置
     * @param arr 表示完全二叉树的数组
     * @param root 当前的根节点
     * @param len 数组中，堆的长度
     */
    private static void heapity(int[] arr, int root, int len) {
        // 计算左右节点的在数组中的位置
        int left = (root << 1) + 1;
        int right = (root << 1) + 2;
        // 初始化当前子树的最大值的位置为根节点的位置
        int max = root;

        // 判断左节点是否越界，若没有越界，则判断左节点是否大于根节点
        // 若大于，则将max记录为左节点的下标
        if (left < len && arr[left] > arr[max]) {
            max = left;
        }

        // 判断右节点是否越界，若没有越界，再判断右节点的值是否大于max节点的值
        // 若大于，则更新，max的值为右节点下标
        if (right < len && arr[right] > arr[max]) {
            max = right;
        }

        // 判断当前的最大值节点是否为根节点，若不是，则将最大值节点与根节点交换
        if (root != max) {
            swap(arr, root, max);
            // 递归交换子树的节点
            heapity(arr, max, len);
        }
    }


    /**
     * 交换数组中两个位置的值
     * @param arr
     * @param l
     * @param r
     */
    private static void swap(int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
}

参考博客

https://www.cnblogs.com/lanhaicode/p/10546257.html

https://www.cnblogs.com/Java3y/p/8639937.html

https://www.jianshu.com/p/0d383d294a80