java编程
搜索
分类

Java实现二叉堆、大顶堆和小顶堆

作者：炒鸡辣鸡123 时间：2022-08-20 18:39:33　

什么是二叉堆

二叉堆就是完全二叉树，或者是靠近完全二叉树结构的二叉树。在二叉树建树时采取前序建树就是建立的完全二叉树。也就是二叉堆。所以二叉堆的建堆过程理论上讲和前序建树一样。

什么是大顶堆、小顶堆

二叉堆本质上是一棵近完全的二叉树，那么大顶堆和小顶堆必然也是满足这个结构要求的。在此之上，大顶堆要求对于一个节点来说，它的左右节点都比它小；小顶堆要求对于一个节点来说，它的左右节点都比它大。

建堆

二叉堆建堆本质上和前序建堆差不多，只不过需要考虑的一点就是大小关系，这一点和二叉搜索树建树有点相似，所以可以得出结论，建树，本质上都是递归建树，只不过因为数据结构的大小要求不一样，需要的判断函数不一样，节点进入哪个位置也不一样。

大顶堆和小顶堆也分为稳定和不稳定的堆。稳定和不稳定指如果具备相同的值，那么他们的插入顺序应该和节点顺序一致。

程序实现

首先，定义出基本的堆结构

public class BinaryHeap {

    private Integer value;

    private BinaryHeap leftChild;
    private BinaryHeap rightChild;
}

建堆过程与建二叉树过程一致

public static BinaryHeap buildHeap(BinaryHeap binaryHeap, Integer value) {
    if (Objects.isNull(binaryHeap)) binaryHeap = new BinaryHeap();
    if (Objects.isNull(binaryHeap.getValue())) {
        binaryHeap.setValue(value);
        return binaryHeap;
    }
    if (Objects.isNull(binaryHeap.getLeftChild())) {
        BinaryHeap binaryHeap1 = new BinaryHeap();
        binaryHeap1.setValue(value);
        binaryHeap.setLeftChild(binaryHeap1);
    } else if (Objects.nonNull(binaryHeap.getLeftChild())) {
        if (Objects.isNull(binaryHeap.getRightChild())) {
            BinaryHeap binaryHeap1 = new BinaryHeap();
            binaryHeap1.setValue(value);
            binaryHeap.setRightChild(binaryHeap1);
        } else {
            // TODO: 2022/1/14 左右节点两种都不为null
            if (checkNull(binaryHeap.getLeftChild())) buildHeap(binaryHeap.getLeftChild(), value);
            else if (checkNull(binaryHeap.getRightChild())) buildHeap(binaryHeap.getRightChild(), value);
            else buildHeap(binaryHeap.getLeftChild(), value);
        }

    }
    return binaryHeap;
}

主要原理就是如果当前节点的左节点为空，则把当前值放到左节点，如果左节点不为空，右节点为空，则把值放到右节点。如果左右节点都不为空，就将建树过程转移到下一层，如果左节点有为空的子节点，就转移给左节点，如果左节点没有为空的子节点，且右节点有为空的子节点，那么转移给右节点。如果左右节点都没有为空的子节点，那么也转移给左节点。

以序列2,3,4,5,9,6,8,7为例，按照该算法建立出来的二叉堆结构如下：

{
   "value": 2,
   "left_child": {
       "value": 3,
       "left_child": {
           "value": 4,
           "left_child": {
               "value": 8,
               "left_child": null,
               "right_child": null
           },
           "right_child": {
               "value": 7,
               "left_child": null,
               "right_child": null
           }
       },
       "right_child": {
           "value": 5,
           "left_child": null,
           "right_child": null
       }
   },
   "right_child": {
       "value": 1,
       "left_child": {
           "value": 9,
           "left_child": null,
           "right_child": null
       },
       "right_child": {
           "value": 6,
           "left_child": null,
           "right_child": null
       }
   }
}

建立大顶堆

大顶堆在建堆的基础上，有一个要求，根节点比左右子树的任何节点的值都大。那么建树的过程可以分为两步，对于每一个值，首先按照建树过程，会到二叉堆的最底部，然后通过不断的让自己与自己的根节点做比较，如果自己大于根节点，就交换自己与根节点的位置，递归回溯即可。

逻辑过程

Java实现二叉堆、大顶堆和小顶堆

假设现在红色节点组成的已经是一个大顶堆，现在新增了一个节点到这个二叉堆中，而且是比任意节点都大，那么黑色箭头将是该节点的行动路线，它会反复与父级比较，如果大于父级，则交换和父级的关系。

程序实现

public static BinaryHeap up(BinaryHeap father) {
 if (Objects.nonNull(father.getLeftChild())) {
   if (father.getValue() < father.getLeftChild().getValue()) {
     int c = father.getValue();
     father.setValue(father.getLeftChild().getValue());
     father.getLeftChild().setValue(c);
   }
   up(father.getLeftChild());
 }
 if (Objects.nonNull(father.getRightChild())) {
   if (father.getValue() < father.getRightChild().getValue()) {
     int c = father.getValue();
     father.setValue(father.getRightChild().getValue());
     father.getRightChild().setValue(c);
   }
   up(father.getRightChild());
 }
 return father;
}

该方法放在普通建树方法之后，就是大顶堆的建树方法了，总的方法如下：

public static BinaryHeap bigPush(BinaryHeap binaryHeap, Integer value) {
   binaryHeap = buildHeap(binaryHeap, value);
   up(binaryHeap);
   return binaryHeap;
}

还是以序列2,3,4,5,9,6,8,7为例，按照该算法建立出来的大顶堆结构如下：

{
   "value": 9,
   "left_child": {
       "value": 8,
       "left_child": {
           "value": 7,
           "left_child": {
               "value": 2,
               "left_child": null,
               "right_child": null
           },
           "right_child": {
               "value": 4,
               "left_child": null,
               "right_child": null
           }
       },
       "right_child": {
           "value": 3,
           "left_child": null,
           "right_child": null
       }
   },
   "right_child": {
       "value": 6,
       "left_child": {
           "value": 1,
           "left_child": null,
           "right_child": null
       },
       "right_child": {
           "value": 5,
           "left_child": null,
           "right_child": null
       }
   }
}

建立小顶堆

小顶堆与大顶堆类似

逻辑过程

Java实现二叉堆、大顶堆和小顶堆

过程与大顶堆一致，不过此时是比父级小就和父级交换。

程序实现

public static BinaryHeap down(BinaryHeap father) {
   if (Objects.nonNull(father.getLeftChild())) {
       if (father.getValue() > father.getLeftChild().getValue()) {
           int c = father.getValue();
           father.setValue(father.getLeftChild().getValue());
           father.getLeftChild().setValue(c);
       }
       down(father.getLeftChild());
   }
   if (Objects.nonNull(father.getRightChild())) {
       if (father.getValue() > father.getRightChild().getValue()) {
           int c = father.getValue();
           father.setValue(father.getRightChild().getValue());
           father.getRightChild().setValue(c);
       }
       down(father.getRightChild());
   }
   return father;
}

这个是向下走的过程，最终代码为：

public static BinaryHeap smallPush(BinaryHeap binaryHeap, Integer value) {
   binaryHeap = buildHeap(binaryHeap, value);
   down(binaryHeap);
   return binaryHeap;
}

以序列2,3,4,5,9,6,8,7为例，按照该算法建立出来的小顶堆结构如下：

{
   "value": 1,
   "left_child": {
       "value": 3,
       "left_child": {
           "value": 4,
           "left_child": {
               "value": 8,
               "left_child": null,
               "right_child": null
           },
           "right_child": {
               "value": 7,
               "left_child": null,
               "right_child": null
           }
       },
       "right_child": {
           "value": 5,
           "left_child": null,
           "right_child": null
       }
   },
   "right_child": {
       "value": 2,
       "left_child": {
           "value": 9,
           "left_child": null,
           "right_child": null
       },
       "right_child": {
           "value": 6,
           "left_child": null,
           "right_child": null
       }
   }
}

从堆顶取数据并重构大小顶堆

public static Integer bigPop(BinaryHeap binaryHeap) {
   Integer val = binaryHeap.getValue();
   if (binaryHeap.getLeftChild().getValue() >= binaryHeap.getRightChild().getValue()) {
       binaryHeap.setValue(binaryHeap.getLeftChild().getValue());
       BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getLeftChild().getLeftChild(), binaryHeap.getLeftChild().getRightChild());
       up(binaryHeap1);
       binaryHeap.setLeftChild(binaryHeap1);
   } else {
       binaryHeap.setValue(binaryHeap.getRightChild().getValue());
       BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getRightChild().getLeftChild(), binaryHeap.getRightChild().getRightChild());
       up(binaryHeap1);
       binaryHeap.setRightChild(binaryHeap1);
   }
   return val;
}

public static Integer smallPop(BinaryHeap binaryHeap) {
   Integer val = binaryHeap.getValue();
   if (binaryHeap.getLeftChild().getValue() <= binaryHeap.getRightChild().getValue()) {
       binaryHeap.setValue(binaryHeap.getLeftChild().getValue());
       BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getLeftChild().getLeftChild(), binaryHeap.getLeftChild().getRightChild());
       down(binaryHeap1);
       binaryHeap.setLeftChild(binaryHeap1);
   } else {
       binaryHeap.setValue(binaryHeap.getRightChild().getValue());
       BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getRightChild().getLeftChild(), binaryHeap.getRightChild().getRightChild());
       down(binaryHeap1);
       binaryHeap.setRightChild(binaryHeap1);
   }
   return val;

}

取出来之后，需要重新调用down或者up函数。以构建小顶堆，取出五次后的结果

public static void main(String[] args) {
       int[] a = new int[]{2, 3, 1, 4, 5, 9, 6, 8, 7};

BinaryHeap binaryHeap = new BinaryHeap();
       for (int i = 0; i < a.length; i++) {
           binaryHeap = smallPush(binaryHeap, a[i]);
       }
       System.out.println(Json.toJson(smallPop(binaryHeap)));
       System.out.println(Json.toJson(smallPop(binaryHeap)));
       System.out.println(Json.toJson(smallPop(binaryHeap)));
       System.out.println(Json.toJson(smallPop(binaryHeap)));
       System.out.println(Json.toJson(smallPop(binaryHeap)));
       System.out.println(Json.toJson(binaryHeap));
   }

取完后的小顶堆为：

{
   "value": 6,
   "left_child": {
       "value": 7,
       "left_child": {
           "value": 8,
           "left_child": null,
           "right_child": null
       },
       "right_child": null
   },
   "right_child": {
       "value": 9,
       "left_child": null,
       "right_child": null
   }
}

来源：https://blog.csdn.net/xielinrui123/article/details/122629751

标签：Java,二叉堆,大顶堆,小顶堆
0
投稿

猜你喜欢

  • java读取cvs文件并导入数据库

    2023-11-25 01:23:13

  • java实现日期拆分的方法

    2023-06-19 00:28:59

  • Flutter 图片开发核心技能快速掌握教程

    2023-08-16 22:01:51

  • SpringBoot FreeWorker模板技术解析

    2023-08-09 09:14:39

  • Java CompletableFuture实现多线程异步编排

    2023-07-22 22:57:02

  • SpringBoot实现PPT格式文件上传并在线预览功能

    2023-07-22 14:44:56

  • 详解Spring缓存注解@Cacheable,@CachePut , @CacheEvict使用

    2021-11-18 12:18:05

  • java实现字符串四则运算公式解析工具类的方法

    2021-11-03 09:22:23

  • iOS实现微信朋友圈与摇一摇功能

    2023-06-16 13:59:48

  • 50 道Java 线程面试题(经典）

    2023-11-23 19:47:37

  • IDEA解决springboot热部署失效问题(推荐)

    2023-08-12 10:40:49

  • IDEA + Maven环境下的SSM框架整合及搭建过程

    2023-08-26 02:06:55

  • Java操作Mongodb数据库实现数据的增删查改功能示例

    2023-11-25 00:02:05

  • Java开发中可以防止界面假死的刷新代码

    2023-11-23 22:23:41

  • GSON实现Java对象与JSON格式对象相互转换的完全教程

    2023-11-23 09:23:37

  • 浅析Java多线程同步synchronized

    2023-05-20 15:52:29

  • SpringBoot整合之SpringBoot整合MongoDB的详细步骤

    2023-11-25 09:55:37

  • java中申请不定长度数组ArrayList的方法

    2023-02-24 17:37:37

  • java 动态生成bean的案例

    2023-08-09 02:20:05

  • mybatis源码解读之executor包懒加载功能 

    2022-09-17 00:28:05
    • asp之家 软件编程 m.aspxhome.com