1 堆

堆是一种特殊的树,它需要满足两个要求:

  1. 堆是一棵完全二叉树
  2. 堆中每一个节点的值必须大于等于(或小于等于)其子树中每个节点的值

根据第二个特性可以细分出大顶堆和小顶堆

1.1 如何存储堆中节点

直接使用数组存储即可,数组下标为 0 的位置空着,从数组下标为 1 的位置开始存储,假设某个节点的数组下标为 i,它的左子树节点下标为 i * 2,右子树下标为 i * 2 + 1。

使用数组存储堆

1.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
// 往堆中插入一个元素的代码实现
// 这里的实现考虑的是大顶堆的情况
public class Heap {
    // 数组,从下标1开始存储数据
    private int[] heapData;
    // 堆可以存储的最大数据个数
    private int capacity;
    // 堆中已经存储的数据个数
    private int size;

    public Heap(int capacity) {
        heapData = new int[capacity + 1];
        this.capacity = capacity;
        size = 0;
    }

    public void insert(int data) {
        if (size >= capacity)
            // 堆满了
            return;
        ++size;
        heapData[size] = data;
        int i = size;
        // 自下往上堆化
        // 循环直到 i/2 == 0 为止
        // 当 i/2 == 0 表示没有父节点了
        while (
            // 父节点存在
                i / 2 > 0
                        // 且子节点比父节点大
                        && heapData[i] > heapData[i / 2]
        ) {
            // 交换自节点和父节点的值
            swap(heapData, i, i / 2);
            // 将父节点的下标赋值给子节点
            i = i / 2;
        }
    }

    private static void swap(int[] a, int i1, int i2) {
        int temp = a[i1];
        a[i1] = a[i2];
        a[i2] = temp;
    }
}

1.3 删除堆顶元素

根据堆定义的第二条,任何检点的值都大于等于(或小于等于)子树节点的值,我们就可以发现,堆顶元素存储的就是堆中数据的最大值或者最小值。

删除堆顶元素之后,我们将数组中最后一个元素放到堆顶,然后再次完成堆化就完成了删除堆顶元素的过程。

 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
// 大顶堆删除堆顶元素的代码实现
public class Heap {
    // 数组,从下标1开始存储数据
    private int[] heapData;
    // 堆可以存储的最大数据个数
    private int capacity;
    // 堆中已经存储的数据个数
    private int size;

    public Heap(int capacity) {
        heapData = new int[capacity + 1];
        this.capacity = capacity;
        size = 0;
    }

    public void removeMax() {
        if (size == 0)
            // 堆中没有数据
            return;
        // 将堆的最后一个数据赋值给堆顶数据
        heapData[1] = heapData[size];
        --size;
        heapify(heapData, size, 1);
    }

    // 自上往下堆化
    private void heapify(int[] a, int size, int currIndex) {
        while (true) {
            int maxIndex = currIndex;
            if (
                    // 存在左节点
                    currIndex * 2 <= size
                            // 且父节点小于左节点
                            && a[currIndex] < a[currIndex * 2]
            ) {
                // 更新最大 index 为左节点
                maxIndex = currIndex * 2;
            }
            if (
                    // 存在右节点
                    currIndex * 2 + 1 <= size
                            // 且父节点大于右节点
                            && a[maxIndex] < a[currIndex * 2 + 1]
            ) {
                // 更新最大 index 为右节点
                maxIndex = currIndex * 2 + 1;
            }
            // 当最大 index 等于当前 index 时,堆化完成
            if (maxIndex == currIndex) break;
            // 交换 currIndex 和 maxIndex 的数组值
            swap(a, currIndex, maxIndex);
            // 将最大 index 赋值给当前 index
            // 在交换过后,最大 index 存储的其实就是之前的 index
            currIndex = maxIndex;
        }
    }

    private static void swap(int[] a, int i1, int i2) {
        int temp = a[i1];
        a[i1] = a[i2];
        a[i2] = temp;
    }
}

1.4 如何创建一个堆

两个思路:

第一种是建一个空堆,然后向堆里面依次插入数据

第二种是自下往上对数组进行堆化

下面是第二种方式的代码实现和示例图片

 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
    public static void buildHeap(
            int[] heapData,
            // 这里的 size 需要去掉 index = 0 的元素
            // 所以 size = length - 1
            int size
    ) {
        for (
                // 初始化的第一个节点是最后一个节点的父节点
                int currIndex = size / 2;
                currIndex >= 1; --currIndex) {
            // 对整个子树进行堆化
            heapify(heapData, size, currIndex);
        }
    }

    private static void heapify(int[] heapData, int size, int currIndex) {
        while (true) {
            int maxIndex = currIndex;
            if (
                    // 如果当前节点的右节点存在
                    currIndex * 2 <= size
                            // 且当前节点的数值小于右节点
                            && heapData[currIndex] < heapData[currIndex * 2]
            ) {
                // 将最大 index 设为右节点
                maxIndex = currIndex * 2;
            }
            if (
                    // 如果当前节点的左节点存在
                    currIndex * 2 + 1 <= size
                            // 且当前节点的数值小于左节点
                            && heapData[maxIndex] < heapData[currIndex * 2 + 1]
            ) {
                // 将最大 index 设为左节点
                maxIndex = currIndex * 2 + 1;
            }
            // 如果最大 index 等于当前 index 则完成堆化
            if (maxIndex == currIndex) break;
            // 交换 maxIndex 存的数值与 currIndex 存的数值
            swap(heapData, currIndex, maxIndex);
            // 由于上一步数值交换了,随意这里需要将 index 也进行交换
            currIndex = maxIndex;
        }
    }

    private static void swap(int[] a, int i1, int i2) {
        int temp = a[i1];
        a[i1] = a[i2];
        a[i2] = temp;
    }

    public static void main(String[] args) {
        int[] arrHeap = new int[]{0, 7, 16, 20, 13, 4, 1, 19, 5, 8, 2, 3};
        buildHeap(arrHeap, arrHeap.length - 1);
    }

示例图片

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
    public static void sort(int[] heapData, int size) {
        // 构建堆
        buildHeap(heapData, size);
        int currSize = size;
        // 当 currIndex == 1 的时候说明已经排序完毕了
        while (currSize > 1) {
            swap(heapData, 1, currSize);
            --currSize;
            // 堆化
            heapify(heapData, currSize, 1);
        }
    }

    public static void buildHeap(
            int[] heapData,
            // 这里的 size 需要去掉 index = 0 的元素
            // 所以 size = length - 1
            int size
    ) {
        for (
                // 初始化的第一个节点是最后一个节点的父节点
                int currIndex = size / 2;
                currIndex >= 1; --currIndex) {
            // 对整个子树进行堆化
            heapify(heapData, size, currIndex);
        }
    }

    private static void heapify(int[] heapData, int size, int currIndex) {
        while (true) {
            int maxIndex = currIndex;
            if (
                    // 如果当前节点的右节点存在
                    currIndex * 2 <= size
                            // 且当前节点的数值小于右节点
                            && heapData[currIndex] < heapData[currIndex * 2]
            ) {
                // 将最大 index 设为右节点
                maxIndex = currIndex * 2;
            }
            if (
                    // 如果当前节点的左节点存在
                    currIndex * 2 + 1 <= size
                            // 且当前节点的数值小于左节点
                            && heapData[maxIndex] < heapData[currIndex * 2 + 1]
            ) {
                // 将最大 index 设为左节点
                maxIndex = currIndex * 2 + 1;
            }
            // 如果最大 index 等于当前 index 则完成堆化
            if (maxIndex == currIndex) break;
            // 交换 maxIndex 存的数值与 currIndex 存的数值
            swap(heapData, currIndex, maxIndex);
            // 由于上一步数值交换了,随意这里需要将 index 也进行交换
            currIndex = maxIndex;
        }
    }

    private static void swap(int[] a, int i1, int i2) {
        int temp = a[i1];
        a[i1] = a[i2];
        a[i2] = temp;
    }

    public static void main(String[] args) {
        int[] arrHeap = new int[]{0, 7, 16, 20, 13, 4, 1, 19, 5, 8, 2, 3};
        sort(arrHeap, arrHeap.length - 1);
        System.out.println(Arrays.toString(arrHeap));
    }

3 为什么快速排序比堆排序快

  1. 堆排序由于它访问数组下标老是跳着访问,比如说 1,2,4,8,这样访问对 CPU 的缓存不友好
  2. 堆排序由于每次交换之后需要重新堆化,所以实际交换次数比快速排序多

堆化图例