文章详情

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

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java堆代码怎么写

2023-06-28 22:30

关注

这篇文章主要介绍了Java堆代码怎么写的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇Java堆代码怎么写文章都会有所收获,下面我们一起来看看吧。

1、堆的定义

①、它是完全二叉树,除了树的最后一层节点不需要是满的,其它的每一层从左到右都是满的。注意下面两种情况,第二种最后一层从左到右中间有断隔,那么也是不完全二叉树。

Java堆代码怎么写

②、它通常用数组来实现。  

Java堆代码怎么写

这种用数组实现的二叉树,假设节点的索引值为index,那么:

节点的左子节点是 2*index+1,

节点的右子节点是 2*index+2,

节点的父节点是 (index-1)/2。

③、堆中的每一个节点的关键字都大于(或等于)这个节点的子节点的关键字。

这里要注意堆和前面说的二叉搜索树的区别,二叉搜索树中所有节点的左子节点关键字都小于右子节点关键字,在二叉搜索树中通过一个简单的算法就可以按序遍历节点。但是在堆中,按序遍历节点是很困难的,如上图所示,堆只有沿着从根节点到叶子节点的每一条路径是降序排列的,指定节点的左边节点或者右边节点,以及上层节点或者下层节点由于不在同一条路径上,他们的关键字可能比指定节点大或者小。所以相对于二叉搜索树,堆是弱序的。

2、遍历和查找

前面我们说了,堆是弱序的,所以想要遍历堆是很困难的,基本上,堆是不支持遍历的。

对于查找,由于堆的特性,在查找的过程中,没有足够的信息来决定选择通过节点的两个子节点中的哪一个来选择走向下一层,所以也很难在堆中查找到某个关键字。

因此,堆这种组织似乎非常接近无序,不过,对于快速的移除最大(或最小)节点,也就是根节点,以及能快速插入新的节点,这两个操作就足够了。

3、移除

移除是指删除关键字最大的节点(或最小),也就是根节点。

根节点在数组中的索引总是0,即maxNode = heapArray[0];

移除根节点之后,那树就空了一个根节点,也就是数组有了一个空的数据单元,这个空单元我们必须填上。

第一种方法:将数组所有数据项都向前移动一个单元,这比较费时。

第二种方法:

具体步骤如下:

Java堆代码怎么写

图a表示把最后一个节点移到根节点,图b、c、d表示将节点向下筛选到合适的位置,它的合适位置在最底层(有时候可能在中间),图e表示节点在正确位置的情景。

注意:向下筛选的时候,将目标节点和其子节点比较,谁大就和谁交换位置。

4、插入

插入节点也很容易,插入时,选择向上筛选,节点初始时插入到数组最后第一个空着的单元,数组容量大小增一。然后进行向上筛选的算法。

注意:向上筛选和向下不同,向上筛选只用和一个父节点进行比较,比父节点小就停止筛选了。

Java堆代码怎么写

5、完整的Java堆代码

首先我们要知道用数组表示堆的一些要点。若数组中节点的索引为x,则:

节点的左子节点是 2*index+1,

节点的右子节点是 2*index+2,

节点的父节点是 (index-1)/2。

注意:"/" 这个符号,应用于整数的算式时,它执行整除,且得到是是向下取整的值。

package com.ys.tree.heap; public class Heap {         private Node[] heapArray;    private int maxSize;    private int currentSize;         public Heap(int mx) {        maxSize = mx;        currentSize = 0;        heapArray = new Node[maxSize];    }         public boolean isEmpty() {        return (currentSize == 0)? true : false;    }         public boolean isFull() {        return (currentSize == maxSize)? true : false;    }         public boolean insert(int key) {        if(isFull()) {            return false;        }        Node newNode = new Node(key);        heapArray[currentSize] = newNode;        trickleUp(currentSize++);        return true;    }    //向上调整    public void trickleUp(int index) {        int parent = (index - 1) / 2; //父节点的索引        Node bottom = heapArray[index]; //将新加的尾节点存在bottom中        while(index > 0 && heapArray[parent].getKey() < bottom.getKey()) {            heapArray[index] = heapArray[parent];            index = parent;            parent = (parent - 1) / 2;        }        heapArray[index] = bottom;    }         public Node remove() {        Node root = heapArray[0];        heapArray[0] = heapArray[--currentSize];        trickleDown(0);        return root;    }    //向下调整    public void trickleDown(int index) {        Node top = heapArray[index];        int largeChildIndex;        while(index < currentSize/2) { //while node has at least one child            int leftChildIndex = 2 * index + 1;            int rightChildIndex = leftChildIndex + 1;            //find larger child            if(rightChildIndex < currentSize &&  //rightChild exists?                    heapArray[leftChildIndex].getKey() < heapArray[rightChildIndex].getKey()) {                largeChildIndex = rightChildIndex;            }            else {                largeChildIndex = leftChildIndex;            }            if(top.getKey() >= heapArray[largeChildIndex].getKey()) {                break;            }            heapArray[index] = heapArray[largeChildIndex];            index = largeChildIndex;        }        heapArray[index] = top;    }    //根据索引改变堆中某个数据    public boolean change(int index, int newValue) {        if(index < 0 || index >= currentSize) {            return false;        }        int oldValue = heapArray[index].getKey();        heapArray[index].setKey(newValue);        if(oldValue < newValue) {            trickleUp(index);        }        else {            trickleDown(index);        }        return true;    }         public void displayHeap() {        System.out.println("heapArray(array format): ");        for(int i = 0; i < currentSize; i++) {            if(heapArray[i] != null) {                System.out.print(heapArray[i].getKey() + " ");            }            else {                System.out.print("--");            }        }    }}class Node {    private int iData;    public Node(int key) {        iData = key;    }         public int getKey() {        return iData;    }         public void setKey(int key) {        iData = key;    }}

关于“Java堆代码怎么写”这篇文章的内容就介绍到这里,感谢各位的阅读!相信大家对“Java堆代码怎么写”知识都有一定的了解,大家如果还想学习更多知识,欢迎关注编程网行业资讯频道。

阅读原文内容投诉

免责声明:

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

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

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯