树形结构----最大堆与优先队列

标签: 数据结构与算法

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

package 树形结构;

import shixianClass.ArrayList;

import java.util.Iterator;

//最大堆
public class MaxHeap<E extends Comparable<E>> implements Iterable<E> {
    //用ArrayList当做最大堆的存储容器
    private ArrayList<E> data;
    public MaxHeap(){
        data=new ArrayList<>();
    }
    //获取父结点的角标
    private int parent(int k){
        if(k<=0){
            throw new IllegalArgumentException("没有父结点");
        }
        return (k-1)/2;
    }

    //获取左孩子结点的角标
    private int leftChild(int k){
        return 2*k+1;
    }
    //获取左孩子结点的角标
    private int rightChild(int k){
        return 2*k+2;
    }

    public int size(){
        return data.size();
    }
    public  boolean isEmpty(){
        return data.isEmpty();
    }

    public void clear(){
        data.clear();
    }
    //向最大堆中添加一个元素E
    public void add(E e){
        data.add(e);
        siftUp(data.size()-1);
    }
    //将角标K所对应的元素上浮
    private void siftUp(int k) {
        while (k>0&&data.get(k) .compareTo(data.get(parent(k)))>0){
              data.swap(k,parent(k));
              k=parent(k);
        }
    }

    //查找最大值
    public E findMax(){
        if(data.isEmpty()){
            throw new IllegalArgumentException("最大堆为空");
        }
        return data.get(0);
    }
    //查找最小值
    public E findMin(){
        if(data.isEmpty()){
            throw new IllegalArgumentException("最大堆为空");
        }
        E min=data.get(0);
        for (int i=1;i<data.size();i++){
            if (data.get(i).compareTo(min)<0){
                min=data.get(i);
            }
        }
        return min;
    }

    //删除根结点
    public E extractMax(){
        E max=findMax();
        data.swap(0,data.size()-1);
        data.remove(data.size()-1);
        siftDown(0);
        return max;
    }

    //下沉
    private void siftDown(int k) {
        while (leftChild(k)<data.size()){
            int j=leftChild(k);
            if(j+1<data.size()&&data.get(j+1).compareTo(data.get(j))>0){
                j=rightChild(k);
            }
            if(data.get(k).compareTo(data.get(j))<0){
                data.swap(k,j);
                k=j;
            }else {
                break;
            }
        }
    }

    //修改
    public E replace(E e){
        E ret=findMax();
        data.set(0,e);
        siftDown(0);
        return ret;
    }
    @Override
    public Iterator<E> iterator() {
        return data.iterator();
    }

    @Override
    public String toString() {
        return data.toString();
    }
}

测试

package ceshi;

import 树形结构.MaxHeap;

import java.util.Random;

public class TestMaxHeap {
    public static void main(String[] args) {
        MaxHeap<Integer> heap=new MaxHeap<>();
        Random random=new Random();
        for (int i=0;i<10;i++){
            heap.add(random.nextInt(20));
        }
        System.out.println(heap);
        for (int i=0;i<4;i++){
            System.out.println(heap.extractMax());
        }
    }
}

执行结果

ArrayList:10/10[15,14,14,6,13,2,0,1,4,9]
15
14
14
13

优先队列

package 树形结构;

import shujujiegou_interface.Queue;

import java.util.Iterator;

//优先队列
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
    private MaxHeap<E> heap;
    public PriorityQueue(){
        heap=new MaxHeap<>();
    }
    @Override
    public int size() {
        return heap.size();
    }

    @Override
    public boolean isEmpty() {
        return heap.isEmpty();
    }

    @Override
    public void offer(E element) {
          heap.add(element);
    }

    @Override
    public E poll() {
        return heap.extractMax();
    }

    @Override
    public E element() {
        return heap.findMax();
    }

    @Override
    public void clear() {
        heap.clear();
    }

    @Override
    public Iterator<E> iterator() {
        return heap.iterator();
    }

    @Override
    public String toString() {
        return heap.toString();
    }
}

版权声明:本文为ll_j_21原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ll_j_21/article/details/107597161

智能推荐

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

猜你喜欢

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...

[国家集训队]小Z的袜子(莫队)

[国家集训队]小Z的袜子 题目描述 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z把这NN只袜子从1到NN编号,然后从编号LL到RR(LL 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同...