【DS】6.堆知识总结！！！

素颜马尾好姑娘i 2024-04-03 13:03 75阅读 0赞

> 堆（Heap）和栈(Stack)是我们面试过程中很重要的两个概念。不同场景下，含义不同.
> 
> 一般有两种含义。
> 
> 程序内存布局场景下：两种内存管理方式；
> 
> 数据结构场景下：两种常用的数据结构。
> 
> 本文就是我对堆这种数据结构的理解。

#### 文章目录 ####

*   *  一、堆的基本概念、性质及存储方式
     *   *  定义
         *  定义关键点提取
         *  堆的性质
         *  堆的存储方式
         *  图示
     *  二、堆的创建【两种方式，but都是向下调整】
     *   *  关于向上向下调整
         *  大根堆的创建
         *   *  思路分析
             *  图示分析
             *  代码实现
         *  小根堆的创建
         *   *  思路分析
             *  图示分析
             *  代码实现
         *  建堆时间复杂度求解
     *  三、堆的插入与删除
     *   *  堆的插入
         *   *  思路分析
             *  图示分析
             *  代码实现
         *  堆的删除
         *   *  思路分析
             *  图示分析
             *  代码实现

### 一、堆的基本概念、性质及存储方式 ###

#### 定义 ####

定义：有一个关键码的集合K = \{k0，k1， k2，…，kn-1\}，把它的所有元素按完全二叉树的顺序存储方式存储 在一 个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大  
堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

#### 定义关键点提取 ####

1.  堆是一棵完全二叉树
2.  二叉树中的key值按照二叉树层序遍历的结果存放到一维数组中
3.  根节点的值总是大于/小于左孩子节点和右孩子节点的，但是左孩子和右孩子值大小关系并不确定

#### 堆的性质 ####

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

#### 堆的存储方式 ####

顺序存储：二叉树中的key值按照二叉树层序遍历的结果存放到一维数组中【高效存储】

链式存储：操作较麻烦，应用较少。

**特别注意**

假设i为节点在数组中的下标

*  如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
 *  如果2 \* i + 1 小于节点个数，则节点i的左孩子下标为2 \* i + 1，否则没有左孩子
 *  如果2 \* i + 2 小于节点个数，则节点i的右孩子下标为2 \* i + 2，否则没有右孩子

#### 图示 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-r8mtHDoq-1665900642821)(F:\\typora插图\\image-20221016084031230.png)\]][img-r8mtHDoq-1665900642821_F_typora_image-20221016084031230.png]

### 二、堆的创建【两种方式，but都是向下调整】 ###

#### 关于向上向下调整 ####

> 向上：子过程从下往上，一般是插入操作
> 
> 向下:子过程从根节点到孩子节点，一般是建堆操作和删除操作

#### 大根堆的创建 ####

##### 思路分析 #####

1.  每棵子树都应该是大根堆
2.  从下往上调整
3.  ①从最后一颗子树的根节点开始调整②然后 减减调整其他的根节点③之后，为确保调整根节点的孩子节点作为根节点的堆是大根堆，设置shitDown子函数
4.  怎么找到最后一棵子树的根节点

【说明：虽然我们说堆是一棵二叉树，但是实际堆创建时给的是数组，我们根据数组创建即可】

##### 图示分析 #####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sbzbYCyA-1665900619347)(F:\\typora插图\\image-20221016132650135.png)\]][img-sbzbYCyA-1665900619347_F_typora_image-20221016132650135.png]

##### 代码实现 #####

public void createHeap(){
        
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
        
            shitDown(parent,usedSize);
        }
    }
    private void shitDown(int parent,int len){
        
        int child=2*parent+1;
        while(child<len){
        
            if((child+1<len)&&(elem[child]<elem[child+1])){
        
                child++;
            }
            if(elem[child]>elem[parent]){
        
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent+1;
            }else{
        
                break;
            }
        }
    }

#### 小根堆的创建 ####

##### 思路分析 #####

1.  思路与大根堆类似
2.  只需要将函数中逻辑比较部分的大于换成小于即可

##### 图示分析 #####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JkyW2Scr-1665900619348)(F:\\typora插图\\image-20221016133502589.png)\]][img-JkyW2Scr-1665900619348_F_typora_image-20221016133502589.png]

##### 代码实现 #####

public void createHeap(){
        
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
        
            shitDownSmall(parent,usedSize);
        }
    }
    private void shitDownSmall(int parent, int len){
        
        int child=2*parent+1;
        while(child<len){
        
            if((child+1<len)&&(elem[child]>elem[child+1])){
        
                child++;
            }
            if(elem[child]<elem[parent]){
        
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent+1;
            }else{
        
                break;
            }
        }
    }

#### 建堆时间复杂度求解 ####

**时间复杂度**

*  调整（即shitDown子函数）的时间复杂度是O(logn)【树的高度】
 *  建堆的时间复杂度是`O(n)`

**过程分析**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tDHRujZM-1665900619350)(F:\\typora插图\\image-20221016140451913.png)\]][img-tDHRujZM-1665900619350_F_typora_image-20221016140451913.png]

### 三、堆的插入与删除 ###

> 对于一般的数据结构，我们一般讨论它的增删查改操作，那为什么我们这里只讨论堆的插入和删除呢？
> 
> 查找和更改操作一般基于索引，一般是查找指定下标 的，但是堆并没有索引概念。这样的操作很少用。
> 
> 但是堆有时也让查堆顶的值。

#### 堆的插入 ####

##### 思路分析 #####

1.  插入之后，仍然要保证得到的是大根堆
2.  用的是向上调整shitUp
3.  原来就是一个大根堆，所以只需要比较新插入的child和parent
4.  循环截止条件是child<=0/parent>=0

##### 图示分析 #####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5pxQRaiC-1665900619352)(F:\\typora插图\\image-20221016134546939.png)\]][img-5pxQRaiC-1665900619352_F_typora_image-20221016134546939.png]

##### 代码实现 #####

public void offer(int val){
        
        if(isFull()){
        
            elem= Arrays.copyOf(elem,elem.length*2);
        }
        this.elem[usedSize++]=val;
        shitUp(usedSize-1);
    }
    private void shitUp(int child){
        
        int parent=(child-1)/2;
        while(child>0){
        
            if(elem[child]>elem[parent]){
        
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                child=parent;
                parent=(parent-1)/2;
            }else{
        
                break;
            }
        }
    }
    public boolean isFull(){
        
        return usedSize==elem.length;
    }

#### 堆的删除 ####

##### 思路分析 #####

1.  使用的是一个交换
2.  把想要删除的节点和堆顶元素交换，然后向下调整
3.  传的结束位置是usedSize-1，因为已经删除一个节点了

##### 图示分析 #####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-faZg1C9e-1665900619354)(F:\\typora插图\\image-20221016140616855.png)\]][img-faZg1C9e-1665900619354_F_typora_image-20221016140616855.png]

##### 代码实现 #####

public int pop(){
        
        if(isEmpty()){
        
            return -1;
        }
        int tmp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[--usedSize]=tmp;
        shitDown(0,usedSize);
        return tmp;
    }
    public boolean isEmpty(){
        
        return usedSize==0;
    }
    private void shitDown(int parent,int len){
        
        int child=2*parent+1;
        while(child<len){
        
            if((child+1<len)&&(elem[child]<elem[child+1])){
        
                child++;
            }
            if(elem[child]>elem[parent]){
        
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent+1;
            }else{
        
                break;
            }
        }
    }

[img-r8mtHDoq-1665900642821_F_typora_image-20221016084031230.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a8912c54e2ad4e758427ee0bc447ad1e.png
[img-sbzbYCyA-1665900619347_F_typora_image-20221016132650135.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b4d1466673d5447c840122622013c188.png
[img-JkyW2Scr-1665900619348_F_typora_image-20221016133502589.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/47bb0b37fe54407292bafc78744a57ff.png
[img-tDHRujZM-1665900619350_F_typora_image-20221016140451913.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/52072bb3741a4f9b8e4af71c54a8051c.png
[img-5pxQRaiC-1665900619352_F_typora_image-20221016134546939.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d801a73e65084b8cb30d2f765e2afcfb.png
[img-faZg1C9e-1665900619354_F_typora_image-20221016140616855.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/76683b9c2aaa46fc9c67e128a8aafc86.png