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

5次阅读

共计 5674 个字符，预计需要花费 15 分钟才能阅读完成。

堆（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. 堆是非线性数据结构，相当于一维数组，有两个间接后继

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

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

/**
 * 堆接口类
 * 利用场景：* 优先队列
 * 取最大值 / 最小值
 * @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();}

/**
 * 最大堆，也称大跟堆，也称大顶堆
 * @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("");
    }
}

/**
 * 最小堆，也称小跟堆，也称小顶堆
 * @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("");
    }
}

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());

}

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

正文完

java

发表至： java

2021-11-06

0

关于java:一篇博客带你轻松应对java面试中的多线程与高并发

关于java:服务发现与配置管理高可用最佳实践

关于java:软件开发中的开源协议详解

关于java:基于SSM的医院科室人员管理系统

关于人工智能:系统架构一文看懂昇腾达芬奇架构计算单元

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

目录：

1、定义

2、个性

3、名词

4、实操

注释：

一、定义：

二、个性：

三、名词：

四、实操：

1、创立堆接口类：

2、创立最大堆实现类：

3、创立最小堆实现类：

4、测试：

5、后果：

站内搜索