我的编程空间,编程开发者的网络收藏夹
学习永远不晚

详解Java如何实现小顶堆和大顶堆

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

详解Java如何实现小顶堆和大顶堆

大顶堆

每个结点的值都大于或等于其左右孩子结点的值

小顶堆

每个结点的值都小于或等于其左右孩子结点的值

对比图

在这里插入图片描述

实现代码


public class HeapNode{
    private int size;//堆大小
    private int[] heap;//保存堆数组

    //初始化堆
    public HeapNode(int n) {
        heap = new int[n];
        size = 0;
    }

    //小顶堆建堆
    public void minInsert(int key){
        int i = this.size;
        if (i==0) heap[0] = key;
        else {
            while (i>0 && heap[i/2]>key){
                heap[i] = heap[i/2];
                i = i/2;
            }
            heap[i] = key;
        }
        this.size++;
    }

    //大顶堆建堆
    public void maxInsert(int key){
        int i = this.size;
        if (i==0) heap[0] = key;
        else {
            while (i>0 && heap[i/2]<key){
                heap[i] = heap[i/2];
                i = i/2;
            }
            heap[i] = key;
        }
        this.size++;
    }

    //小顶堆删除
    public int minDelete(){
        if (this.size==0) return -1;
        int top = heap[0];
        int last = heap[this.size-1];
        heap[0] = last;
        this.size--;
        //堆化
        minHeapify(0);
        return top;
    }

    //大顶堆删除
    public int maxDelete(){
        if (this.size==0) return -1;
        int top = heap[0];
        int last = heap[this.size-1];
        heap[0] = last;
        this.size--;
        //堆化
        maxHeapify(0);
        return top;
    }

    //小顶堆化
    public void minHeapify(int i){
        int L = 2*i,R=2*i+1,min;
        if (L<=size && heap[L] < heap[i]) min = L;
        else min = i;
        if (R <= size && heap[R] < heap[min]) min = R;
        if (min!=i){
            int t = heap[min];
            heap[min] = heap[i];
            heap[i] = t;
            minHeapify(min);
        }
    }

    //大顶堆化
    public void maxHeapify(int i){
        int L = 2*i,R=2*i+1,max;
        if (L<=size && heap[L] > heap[i]) max = L;
        else max = i;
        if (R <= size && heap[R] > heap[max]) max = R;
        if (max!=i){
            int t = heap[max];
            heap[max] = heap[i];
            heap[i] = t;
            maxHeapify(max);
        }
    }

    //输出堆
    public void print(){
        for (int i = 0; i < this.size; i++) {
            System.out.print(heap[i]+" ");
        }
        System.out.println();
    }
}

测试


public class Heap {
    static int[] a = {5,3,6,4,2,1};
    static int n = a.length;
    public static void main(String[] args){
        HeapNode heapNode = new HeapNode(n);
        for (int i = 0; i < n; i++) {
            heapNode.maxInsert(a[i]);
        }
        heapNode.print();
        for (int i = 0; i < n; i++) {
            int min = heapNode.maxDelete();
            System.out.print("堆顶:"+min+" 剩下堆元素:");
            heapNode.print();
        }
    }
}

结果

在这里插入图片描述

到此这篇关于详解Java如何实现小顶堆和大顶堆的文章就介绍到这了,更多相关Java实现小顶堆和大顶堆内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

详解Java如何实现小顶堆和大顶堆

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

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

这篇文章将为大家详细讲解有关Java如何实现二叉堆、大顶堆和小顶堆,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。什么是二叉堆二叉堆就是完全二叉树,或者是靠近完全二叉树结构的二叉树。在二叉树建树时采取前序建
2023-06-29

Java 堆排序实例(大顶堆、小顶堆)

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序的平均时间复杂度为Ο(nlogn) 。算法步骤:1. 创建
2023-05-30

Java语言如何实现最大堆

这篇文章将为大家详细讲解有关Java语言如何实现最大堆,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。最大堆最大堆的特点是父元素比子元素大,并且是一棵完全二叉树。data[1]开始存,data[0]空着不用
2023-05-30

详解C#如何实现屏幕放大和取色功能

这篇文章主要为大家详细介绍了如何利用C#实现屏幕放大和取色功能,文中的示例代码讲解详细,对我们学习C#有一定的帮助,感兴趣的小伙伴可以了解一下
2022-12-15

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录