堆 超详细的带图总结

今天来总结一下堆数据结构的相关知识。

---

1.堆的概念：

堆是在完全二叉树的基础上进行了条件的限制，即：每个节点都比其孩子节点大则为大堆；每个节点都比其孩子节点小则为小堆。

2.堆的性质：

a.堆中某个节点的值总是不大于或不小于其父节点的值；
b.堆总是一棵完全二叉树。

大堆、小堆示意图：

为什么堆适合使用顺序表（数组）存储呢？
解答：堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储；而对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。

参考如图：

3.堆中双亲节点与孩子节点的关系：

因为堆内部实际上使用数组存储且堆是一颗完全二叉树，所以双亲节点与孩子节点的坐标是有数学关系的，具体如下：
1.如果i为0，则i表示的节点为根节点，否则 双亲节点坐标 = （孩子节点坐标 - 1）/ 2；
2.左孩子坐标 = 2 * 双亲节点坐标 + 1；
3.右孩子坐标 = 2 * 双亲节点坐标 + 2；
…
相关问题拓展：
1.如何知道下标i所在的元素有没有右（左）孩子：判断 2 * i + 2 >= size （右孩子下标是否合法，size为数组长度）。
2.如何知道下标i所在的元素有是不是叶子节点：判断 2 * i + 1 >= size && 2 * i + 2 >= size（即左孩子不存在&&右孩子不存在），简化一下就是 2 * i + 1 >= size ,因为堆是一棵完全二叉树，所以没有左孩子必定没有右孩子。

4.堆的构建：

4.1.堆的向下调整 / 堆化操作（小堆）：

以集合{ 27,15,19,18,28,34,65,49,25,37 }为例，根节点的左右子树已经完全满足小堆的性质，因此只需将根节点向下调整好即可，调整之后的集合顺序为{ 15,18,19,25,28,34,65,49,27,37 }，接下来代码实现做验证。

集合示例：

过程图示：

代码实现：

递归：时间复杂度O(log(n))，空间复杂度：O(n)

public class adjustDown {
    public static void main(String[] args) {
        int[] arr = new int[]{27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        recursionAdjust(arr, 0);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void recursionAdjust(int[] arr, int idx) {
        //默认下标idx的左右孩子中左孩子比较小
        int minIdx = 2 * idx + 1;
        int rightIdx = 2 * idx + 2;
        //若没有左孩子
        if (minIdx >= arr.length) {
            return;
        }
        //若左孩子不是两个孩子中的较小值
        if (rightIdx < arr.length && arr[minIdx] > arr[rightIdx]) {
            minIdx = rightIdx;
        }
        //比较要调整的元素是否大于其孩子的较小值
        if (arr[idx] > arr[minIdx]) {
            swap(arr, idx, minIdx);
            recursionAdjust(arr, minIdx);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
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

迭代：时间复杂度O(log(n))，空间复杂度O(1)

public class adjustDown {
    public static void main(String[] args) {
        int[] arr = new int[]{27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        iterationAdjust(arr, 0);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void iterationAdjust(int[] arr, int idx) {
        //如果idx是叶子节点 则执行
        while (2 * idx + 1 < arr.length) {
            //左右孩子下标
            int minIdx = 2 * idx + 1;
            int rightIdx = 2 * idx + 2;
            if (rightIdx < arr.length && arr[minIdx] > arr[rightIdx]) {
                minIdx = rightIdx;
            }
            //比较要调整的元素是否大于其孩子的较小值
            if (arr[idx] > arr[minIdx]) {
                swap(arr, idx, minIdx);
            }
            idx = minIdx;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
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

4.2.堆的创建（大堆）：

给定无序的序列列{ 1,5,3,8,7,6 }，以创建大堆为例，思路是从尾结点开始，由最后一个节点找到它的双亲节点，然后对其进行向下调整，这样就形成了一个子大堆，然后一直循环操作就可以逐渐形成完整的小堆了。

过程图示：

代码实现：时间复杂度O(n)

public class Operation {
    public static void main(String[] args) {
        int[] arr = new int[]{1,5,3,8,7,6 };
        createHeap(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    //建堆
    public static void createHeap(int[] arr) {
        // 找倒数第一个节点的双亲节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
        //arr.length - 1 为最后一个节点下标，再 - 1 除 2 为它的双亲节点
        int pIdx = (arr.length - 1 - 1) / 2;
        for (; pIdx >= 0; pIdx--) {
            iterationAdjust(arr, pIdx);
        }
    }

    //迭代向下调整
    public static void iterationAdjust(int[] arr, int idx) {
        //如果idx是叶子节点 则执行
        while (2 * idx + 1 < arr.length) {
            //左右孩子下标
            int minIdx = 2 * idx + 1;
            int rightIdx = 2 * idx + 2;
            if (rightIdx < arr.length && arr[minIdx] < arr[rightIdx]) {
                minIdx = rightIdx;
            }
            //比较要调整的元素是否小于其孩子的较大值
            if (arr[idx] < arr[minIdx]) {
                swap(arr, idx, minIdx);
            }
            idx = minIdx;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
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

5.堆的插入与删除：

5.1.插入：

堆的插入总共需要两个步骤：
1.先将元素放入到底层空间中(注意：空间不够时需要扩容)
2. 将最后新插入的节点向上调整，直到满足堆的性质
ps：核心即为向上调整

过程图示：

5.2.删除：

堆的删除一定删除的是堆顶元素。具体如下：
1.将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整

过程图示：