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

堆（Heap）和栈(Stack)是我们面试过程中很重要的两个概念。不同场景下，含义不同.

一般有两种含义。

程序内存布局场景下：两种内存管理方式；

数据结构场景下：两种常用的数据结构。

本文就是我对堆这种数据结构的理解。

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

定义

定义：有一个关键码的集合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，否则没有右孩子

图示

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

关于向上向下调整

向上：子过程从下往上，一般是插入操作

向下:子过程从根节点到孩子节点，一般是建堆操作和删除操作

大根堆的创建

思路分析

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

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

图示分析

代码实现

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. 只需要将函数中逻辑比较部分的大于换成小于即可

图示分析

代码实现

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)

过程分析

三、堆的插入与删除

对于一般的数据结构，我们一般讨论它的增删查改操作，那为什么我们这里只讨论堆的插入和删除呢？

查找和更改操作一般基于索引，一般是查找指定下标 的，但是堆并没有索引概念。这样的操作很少用。

但是堆有时也让查堆顶的值。

堆的插入

思路分析

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

图示分析

代码实现

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，因为已经删除一个节点了

图示分析

代码实现

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;
        }
    }
}