堆超详细的带图总结

àì夳堔傛蜴生んèń 2023-09-28 23:21 31阅读 0赞

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

--------------------

##### 1.堆的概念：  #####

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

##### 2.堆的性质：  #####

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

**大堆、小堆示意图：**

![在这里插入图片描述][564a33439d52467aa04623b5367ecdde.png]

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

参考如图：  
![在这里插入图片描述][294a410e706f48ca860d5158de18feeb.png]

##### 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 \}，接下来代码实现做验证。**

**集合示例：**

![在这里插入图片描述][8ab4dcd6c22d442b9cbffd3d3346e6e7.png]

**过程图示：**  
![在这里插入图片描述][b2d400e9a48f4c15a0bee60cb28123ac.png]

**代码实现：**

**递归：时间复杂度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;
        }
    }

**迭代：时间复杂度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;
        }
    }

4.2.堆的创建（大堆）：

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

**过程图示：**  
![在这里插入图片描述][c64cad9fc08c4ff8b66e6d3ac8d1f54f.png]

**代码实现：时间复杂度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;
        }
    }

##### 5.堆的插入与删除：  #####

5.1.插入：

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

**过程图示：**  
![在这里插入图片描述][cc529170318b417d998bbd693a05fc73.png]

5.2.删除：

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

**过程图示：**  
![在这里插入图片描述][b8be2f15bb444c83a42ebc755f93a753.png]

[564a33439d52467aa04623b5367ecdde.png]: https://img-blog.csdnimg.cn/564a33439d52467aa04623b5367ecdde.png
[294a410e706f48ca860d5158de18feeb.png]: https://img-blog.csdnimg.cn/294a410e706f48ca860d5158de18feeb.png
[8ab4dcd6c22d442b9cbffd3d3346e6e7.png]: https://img-blog.csdnimg.cn/8ab4dcd6c22d442b9cbffd3d3346e6e7.png
[b2d400e9a48f4c15a0bee60cb28123ac.png]: https://img-blog.csdnimg.cn/b2d400e9a48f4c15a0bee60cb28123ac.png
[c64cad9fc08c4ff8b66e6d3ac8d1f54f.png]: https://img-blog.csdnimg.cn/c64cad9fc08c4ff8b66e6d3ac8d1f54f.png
[cc529170318b417d998bbd693a05fc73.png]: https://img-blog.csdnimg.cn/cc529170318b417d998bbd693a05fc73.png
[b8be2f15bb444c83a42ebc755f93a753.png]: https://img-blog.csdnimg.cn/b8be2f15bb444c83a42ebc755f93a753.png