乐趣区

关于java:数据结构之堆初学只需一文

作者：

jiezi

在

目录：

1、定义

2、个性

3、名词

4、实操

注释：

一、定义：

堆（heap）是计算机科学中一类非凡的数据结构的统称。
堆通常是一个能够被看做一棵树的数组对象。

n个元素的序列{k1,k2,ki,…,kn}当且仅当满足以下关系时，称之为堆。
(ki<=k2i且ki<=k2i+1)或者(ki>=k2i且ki>=k2i+1)

解析：
我在这个文章中用的是数组来实现堆，我就用数组举例：
例如：一个数组[2,1,3,4,5,6,7,8]
这个能够当成一个相似齐全二叉树的构造，根当初是2，但还不是堆，而堆分成最大堆，和最小堆，
咱们以最小堆举例，咱们想让这个齐全二叉树的数组，变成堆，就须要调整，
让它们合乎根<=左结点并且根<=右结点，在这里调整咱们也分为两种，
咱们能够用向上调整或者向下调整，当初咱们应用向下调整法，从顶开始往下调整，
而后向下调整只有都须要合乎堆得属性，就能够失去最小堆[1,2,3,4,5,6,7,8]；

以上对定义以及大抵逻辑解析实现，接下来咱们齐全依据这个逻辑解析做实操代码，请急躁往下看

二、个性：

1. 堆中某个结点的值总是不大于或不小于其父结点的值
2. 堆总是一棵齐全二叉树
3. 堆是非线性数据结构，相当于一维数组，有两个间接后继

三、名词：

最大堆/大根堆/大顶堆：
根结点最大的堆

最小堆/小根堆/小顶堆：
根结点最小的堆

四、实操：

1、创立堆接口类：

/**
 * 堆接口类
 * 利用场景：
 * 优先队列
 * 取最大值/最小值
 * @author gxw
 * @date 2021/11/4 早晨21:58
 */
public interface Heap {

    //构建堆办法
    void buildHeap(int[] arr);

    //增加元素
    void add(int g);

    //替换元素，将第i个地位的元素值替换为g
    void replace(int i, int g);

    //删除顶元素
    boolean pop();

    //向上堆排序
    void shift_up(int now);

    //向下堆排序
    void shit_down(int now);

    //获取顶值
    int getTopValue();

    //展现堆
    void display();
}

2、创立最大堆实现类：

/**
 * 最大堆，也称大跟堆，也称大顶堆
 * @author gxw
 * @date 2021/11/4 早晨22:21
 */
public class MaxHeap implements Heap {
    //堆数组
    private int[] heapArr;

    //堆总结点
    private int size;

    //堆深
    private int depth;

    //堆最大寄存结点
    private int maxSize;

    public MaxHeap(int maxSize){
        this.maxSize = maxSize;
        this.heapArr = new int[maxSize];

    }

    @Override
    public void buildHeap(int[] arr) {
        if(arr == null && arr.length <= 0)
            return;
        //进行构建最大堆
        for (int g : arr) {
            add(g);
        }
    }

    @Override
    public void add(int g) {
        //先判断堆是否曾经满了
        if(size == maxSize)
            return;
        //增加到堆得最初
        heapArr[size] = g;
        //结点数加1
        size++;
        //树深判断是否能够加，如果 2^depth -1 < size
        // （原理：通过堆深计算所有总结点值，如果小于以后的堆有结点值，天然须要加1）
        if(Math.pow(2, depth) - 1 < size)
            depth++;
        //向上调整
        shift_up(size);
    }

    @Override
    public void replace(int i, int g) {//i 代表逻辑地位，不代表数组角标，还需减一
        //判断如果角标不在正确范畴内，不能够操作
        if(i < 0 || i > size)
            return;
        //批改值
        heapArr[i - 1] = g;
        //向上调整
        shift_up(i);
    }

    @Override
    public boolean pop() {
        if(size == 0)
            return false;
        //移除最大值(大根值)，并将最初一个值赋给大根值
        heapArr[0] = heapArr[size - 1];
        //结点数量减一
        size--;
        //向下调整, 1代表逻辑第一个值，不代表数组第一个
        shit_down(1);
        return true;
    }

    @Override
    public void shift_up(int now) {//now 逻辑数值，不代表物理数组角标，还需减一
        for(int i = 0;i < depth - 1;i++){
            //获取父结点的地位，因为是数组所以减一
            int parentIndex = (int) Math.floor(now / 2) - 1;
            //replace 办法专有，如果父角标小于0，阐明到顶完结
            if(parentIndex < 0)
                break;
            int nowIndex = now - 1;//因为是数组，所以角标-1
            //判断以后数是否大于父结点，如果大于就替换
            if(heapArr[nowIndex] > heapArr[parentIndex]){
                //替换
                int temp = heapArr[parentIndex];
                heapArr[parentIndex] = heapArr[nowIndex];
                heapArr[nowIndex] = temp;
                //而后从以后持续往上判断
                now = parentIndex + 1;
            }else{//如果不大于，就完结调整
                break;
            }
        }
    }

    @Override
    public void shit_down(int now) {//now 逻辑数值，不代表物理数组角标，还需减一
        for(int i = 0;i < depth - 1;i++){
            //获取左右子结点值最大的地位
            int sonIndex = heapArr[2 * now - 1] > heapArr[2 * now ] ? 2 * now  - 1 : 2 * now ;
            int nowIndex = now - 1;//因为是数组，所以角标-1
            //判断以后数是否小于子结点，如果小于就替换
            if(heapArr[nowIndex] < heapArr[sonIndex]){
                //替换
                int temp = heapArr[sonIndex];
                heapArr[sonIndex] = heapArr[nowIndex];
                heapArr[nowIndex] = temp;
                //而后从以后持续往下判断
                now = sonIndex + 1;
            }else{//如果不小于，就完结调整
                break;
            }
        }
    }

    @Override
    public int getTopValue() {
        return heapArr[0];
    }

    @Override
    public void display() {
        for(int i = 0;i < size;i++){
            System.out.print(heapArr[i] + " ");
        }
        System.out.println("");
    }
}

3、创立最小堆实现类：

/**
 * 最小堆，也称小跟堆，也称小顶堆
 * @author gxw
 * @date 2021/11/4 早晨22:22
 */
public class MinHeap implements Heap {
    //堆数组
    private int[] heapArr;

    //堆总结点
    private int size;

    //堆深
    private int depth;

    //堆最小寄存结点
    private int maxSize;

    public MinHeap(int maxSize){
        this.maxSize = maxSize;
        this.heapArr = new int[maxSize];

    }

    @Override
    public void buildHeap(int[] arr) {
        if(arr == null && arr.length <= 0)
            return;
        //进行构建最小堆
        for (int g : arr) {
            add(g);
        }
    }

    @Override
    public void add(int g) {
        //先判断堆是否曾经满了
        if(size == maxSize)
            return;
        //增加到堆得最初
        heapArr[size] = g;
        //结点数加1
        size++;
        //树深判断是否能够加，如果 2^depth -1 < size
        // （原理：通过堆深计算所有总结点值，如果小于以后的堆有结点值，天然须要加1）
        if(Math.pow(2, depth) - 1 < size)
            depth++;
        //向上调整
        shift_up(size);
    }

    @Override
    public void replace(int i, int g) {//i 代表逻辑地位，不代表数组角标，还需减一
        //判断如果角标不在正确范畴内，不能够操作
        if(i < 0 || i > size)
            return;
        //批改值
        heapArr[i - 1] = g;
        //向上调整
        shift_up(i);
    }

    @Override
    public boolean pop() {
        if(size == 0)
            return false;
        //移除最小值(大根值)，并将最初一个值赋给大根值
        heapArr[0] = heapArr[size - 1];
        //结点数量减一
        size--;
        //向下调整, 1代表逻辑第一个值，不代表数组第一个
        shit_down(1);
        return true;
    }

    @Override
    public void shift_up(int now) {//now 逻辑数值，不代表物理数组角标，还需减一
        for(int i = 0;i < depth - 1;i++){
            //获取父结点的地位，因为是数组所以减一
            int parentIndex = (int) Math.floor(now / 2) - 1;
            //replace 办法专有，如果父角标小于0，阐明到顶完结
            if(parentIndex < 0)
                break;
            int nowIndex = now - 1;//因为是数组，所以角标-1
            //判断以后数是否小于父结点，如果小于就替换
            if(heapArr[nowIndex] < heapArr[parentIndex]){
                //替换
                int temp = heapArr[parentIndex];
                heapArr[parentIndex] = heapArr[nowIndex];
                heapArr[nowIndex] = temp;
                //而后从以后持续往上判断
                now = parentIndex + 1;
            }else{//如果不大于，就完结调整
                break;
            }
        }
    }

    @Override
    public void shit_down(int now) {//now 逻辑数值，不代表物理数组角标，还需减一
        for(int i = 0;i < depth - 1;i++){
            //获取左右子结点值最小的地位
            int sonIndex = heapArr[2 * now - 1] < heapArr[2 * now ] ? 2 * now  - 1 : 2 * now ;
            int nowIndex = now - 1;//因为是数组，所以角标-1
            //判断以后数是否大于子结点，如果大于就替换
            if(heapArr[nowIndex] > heapArr[sonIndex]){
                //替换
                int temp = heapArr[sonIndex];
                heapArr[sonIndex] = heapArr[nowIndex];
                heapArr[nowIndex] = temp;
                //而后从以后持续往下判断
                now = sonIndex + 1;
            }else{//如果不小于，就完结调整
                break;
            }
        }
    }

    @Override
    public int getTopValue() {
        return heapArr[0];
    }

    @Override
    public void display() {
        for(int i = 0;i < size;i++){
            System.out.print(heapArr[i] + " ");
        }
        System.out.println("");
    }
}

4、测试：

public static void main(String[] args) {
    int[] arr = {2,3,3,2,6,7,11,11};

    /**
     * 最大堆，大根堆，大顶堆
     */
    MaxHeap maxHeap = new MaxHeap(20);
    //构建最大堆
    System.out.println("初始构建最大堆");
    maxHeap.buildHeap(arr);
    maxHeap.display();

    //增加数
    System.out.println("增加9");
    maxHeap.add(9);
    maxHeap.display();

    //替换值
    System.out.println("将第6个数值替换成10");
    maxHeap.replace(6, 10);
    maxHeap.display();

    //移除最大值
    System.out.println("移除最大值");
    maxHeap.pop();
    maxHeap.display();

    //获取最大值
    System.out.println("获取最大值");
    System.out.println(maxHeap.getTopValue());

    /**
     * 最小堆，小根堆，小顶堆
     */
    MinHeap minHeap = new MinHeap(20);
    //构建最小堆
    System.out.println("初始构建最小堆");
    minHeap.buildHeap(arr);
    minHeap.display();

    //增加数
    System.out.println("增加1");
    minHeap.add(1);
    minHeap.display();

    //替换值
    System.out.println("将第6个数值替换成10");
    minHeap.replace(6, 10);
    minHeap.display();

    //移除最小值
    System.out.println("移除最小值");
    minHeap.pop();
    minHeap.display();

    //获取最小值
    System.out.println("获取最小值");
    System.out.println(minHeap.getTopValue());

}

5、后果：

—————————————END———————————
本文为数据结构堆得学习总结，心愿能够帮忙到诸位，如果内容有问题，还请贵人指出，谢谢！

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章