堆的认识

下标关系

准备工作

向下调整

建堆

实现

添加元素

删除元素

获取堆顶元素

堆为空判断

堆排序

堆的认识

1. 堆逻辑上是一棵完全二叉树 , 物理上是保存在数组中

2. 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆,反之，则是小堆，或者小根堆，或者最小堆

3. 堆的基本作用是，快速找集合中的最值

 

下标关系

根据堆数组中每个下标,我们可以得出以下结论.

1. 已知双亲(parent)的下标，则：

   • 左孩子(left)下标 = 2 * parent + 1

   • 右孩子(right)下标 = 2 * parent + 2

1. 已知孩子 (不区分左右) (child)下标，则：

   • 双亲(parent)下标 = (child - 1) / 2

准备工作

通过上面我们得知 , 堆是使用数组来存储元素的,只是逻辑上是一颗树,所以我们先构造出个 Heap 类,这个类 用来实现 堆 的操作

public class Heap {
    public int[] elem;	// 存储数据的数组
    public int usedSize;// 记录当前堆中的有效数据

    public Heap(int[] array) {
        this.elem = array;     // 构造参数为一个数组作为参数传进来
        usedSize = array.length;// 这里假设数组元素全部为满的情况
    }
}

向下调整

向下调整:将所有子树是堆,而整棵树本身不是堆的给调整成堆

前提:左右子树必须已经是一个堆才能调整

// 调整前
int[] array = {27,15,19,18,28,34,65,49,25,37};

向下调整算法执行过程

 

//调整后
int[] array = {15, 18, 19, 25, 28, 34, 65, 49, 27};

向下调整代码

//向下调整

public void adjustDown(int parent, int len) {
    int child = 2 * parent + 1;//左子树
    if (child < len){
        //判断左右子树的值谁小
        //判断右子树是否存在
        if (child+1 < len && this.elem[child] > this.elem[child+1]){
            child++;//更改成右子树
        }
        //判断根节点的值是否比孩子节点大
        if(this.elem[parent] > this.elem[child]){
            //交换
            int tmp = this.elem[parent];
            this.elem[parent] = this.elem[child];
            this.elem[child] = tmp;
            //将child节点更新成parent，继续向下调整
            adjustDown(child,len);
        }
    }
}

建堆

通过刚才向下调整算法,我们可以知道,向下调整算法可以将一个子树是堆,而整棵树本身不是堆的给调整成堆,那么 如果给一个 子树也不是堆 的数据,该怎么去调成堆呢?

先给一组数据

// 建堆前
int[] array = {27,19,28,24,36,10,31};		

如果需要将一个看过去只是个完全二叉树,但是不是一个堆的,我们就需要通过算法,把这个树重新构建,构建成一个堆,这个操作叫做 建堆, 这里作者是用建的是小堆 , 建大堆只需要将向下调整算法的比较改一下即可

思路:首先我们需要先找到最后一个父节点 , 前面介绍了下标关系 , 我们可以通过 数组最后一个下标 -1/ 2 找到最后一个父节点,然后从最后一个父节点开始 , 一直调整到根节点树.

// 根据思路 可以得知
int parent = (usedSize - 1) / 2; // 最后一个父节点的位置 

上面说过,通过向下调整算法 ,可以将一个子树是堆,而整棵树本身不是堆的给调整成堆 , 所以 我们可以将最后一个父节点开始的子树,看成一个 子树是堆,而本身不是堆的二叉树

所以我们可以调用向下调整算法 , 将最后一个 子树 先调成小堆

adjustDown(parent,usedSize); // 调用刚写的向下调整算法调整最后一个子树

调整之后,我们可以看到最后一个子树已经是一个堆了

根据上面的一个子树调整过程 , 可以得知,只要将所有的子树构建成堆直到根节点,我们就可以将一颗完全二叉树构建成堆,而且从上图可以看到 parent--操作 就能获取到上一颗子树的根节点 , 所以可以使用循环控制 parent变量 进行建堆 , 代码如下:

public void createHeap() {
        //parent 代表每颗子树的根节点
        for (int parent = (this.usedSize  - 1) / 2; parent >= 0; parent--) {

            adjustDown(parent, this.usedSize);

        }
}

// 建堆后
int[] array = {10, 19, 27, 24, 36, 28, 31};		

接下来我们先看看 堆 的常用操作,堆和栈队列一样,不能随机访问元素, 建堆时建的是小堆,那么堆顶元素一定是这个集合中最小的元素,大堆也是同理

public void offer(int val); // 将指定的元素插入到堆中。  
public int peek(); // 返回堆顶元素  
public int pop(); // 删除元素并返回删除元素   
public boolean isEmpty();// 判断堆是否为空

实现

添加元素

添加元素时,由于堆是数组存储元素,所以我们可以直接使用尾插法进行插入,但需要考虑,如果插入的元素 破坏了堆的结构,那么该怎么处理?

比如 , 目前是一个小堆,我添加的元素比当前堆的元素都小,那么该怎么处理

如果我们添加的元素破坏了堆的结构,这个时候使用 建堆 算法虽然可以重新调整成堆 , 但是建堆需要去遍历每个父节点 , 是有一定的时间开销,如果每次添加元素都建一次堆,那么此时的时间花销就不可小觑了 , 那么此时就有另一种调整算法 向上调整 可以减少时间复杂度

向上调整

向上调整执行流程

 

向上调整代码

public void adjustUp(int child){
    int parent = (child - 1) / 2;
    if(child > 0){
        if(this.elem[child] > this.elem[parent]){
            //交换
            int tmp = this.elem[parent];
            this.elem[parent] = this.elem[child];
            this.elem[child] = tmp;
            // 递归调用向上调整,将父节点作为参数传入
            adjustUp(parent);
        }
    }
}

这样就可以通过向上调整的算法 , 就可以以更短的路径(不用遍历全部父节点),更短的时间去将添加的元素调整到对应的位置上.

添加元素代码

private boolean isFull(){	// 判断数组存放元素是不是已满
        return this.elem.length == this.usedSize;
}

public void offer(int val){
        if(this.isFull()){ 
           this.elem =  Arrays.copyOf(this.elem,this.elem.length * 2);// 扩容代码
        }
        this.elem[this.usedSize] = val;
        adjustUp(this.usedSize - 1);
        this.usedSize++;
}

删除元素

在出队列的时候,并不是直接删除堆顶元素 , 如果直接使用覆盖式方法进行删除的话,不能保证覆盖后的数据是否还是保留的堆的结构(不能确定)

所以这里的思路是: 删除时 , 将堆顶的元素与最后一个元素进行交换 ,之后在删除最后一个元素, 最后通过向下调整的方式把这颗树重新调成堆,这样既能做到删除元素.也能做到不破坏堆的结构

当然这里还要考虑在堆为空的时候 , 调用删除元素操作将要抛出一个异常提示 , 其它根据思路将代码写出即可.

public int pop(){
        if(this.isEmpty()){
            throw new RuntimeException("堆为空");
        }
        int top = this.elem[0]; // 记录堆顶元素,方便返回
    	// 交换
        int tmp = this.elem[0];
        this.elem[0] = this.elem[this.usedSize-1];
        this.elem[this.usedSize-1] = tmp;
        this.usedSize--; // 有效数据减 1
    	// 向下调整,从根节点调整
        adjustDown(0,this.usedSize);
        return top;
}

获取堆顶元素

因为我们的堆是用数组存储数据的,所以返回堆顶的元素也就是返回下标为0的元素

public int peek() {
        if (this.isEmpty()) {
            throw new RuntimeException("堆为空");
        }
        return this.elem[0];
}

堆为空判断

有效数据记录变量为0 既视为 堆里一个元素都没有

public boolean isEmpty() {
        return this.usedSize == 0;
}

到这里,相信大家对 堆 有点印象了,那么接下来作者给大家 扩展一下 使用堆这种数据结构设计的一种排序算法, 也就是常见的 "堆排序"

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

简单点说,在排序的时候,如果想排升序就要建大堆 , 如果需要排降序就要建小堆 , 由于前面作者建堆建的是小堆 , 那这里也就以排升序作为讲解

基本思路: 因为堆的特性 , 在堆顶的一定是最大或最小值,(建大堆为最大值,建小堆为最小值) ,所以通过堆顶的元素跟最后一个元素交换 , 然后向下调整 , 控制好下标长度,就能完成堆排序了

看一下执行过程:

一次排序过程:

从一次排序过程看到 , 交换 能将最小的那个值放到最后面去,向下调整算法可以将第二小的值放到堆顶上,而控制 end 变量能在向下调整的时候不让下标访问到已经有序的元素下标,所以 使用循环控制 end 变量 就能将整个数组排成有序

public void heapSort() {
        int end = this.usedSize - 1; // 有效数据的最后一个元素下标
        while (end > 0) {
            // 交换
            int tmp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = tmp;
            // 从根节点向下调整,end变量控制下标边界
            adjustDown(0, end);
            end--;
        }
}

那么我们来看一下是否能正确排序数据 , 结果是可以的

 

注意: 堆排序的前提要先建堆,升序建大堆,降序建小堆

---

本章到此结束,如果文章有写的不对的地方,欢迎评论区指出,谢谢!