首页 > 编程语言 >优先队列算法

优先队列算法

时间:2022-12-12 16:31:43浏览次数:55  
标签:优先 队列 int 算法 child AnyType array hole currentSize

public class BinaryHeap<AnyType extends Comparable<? super AnyType>> {

private static final int DEFAULT_CAPACITY=10;

private int currentSize;

private AnyType[] array;

public BinaryHeap(){

currentSize=0;

array=null;

enlargeArray(DEFAULT_CAPACITY);

}

/*

* 构造一个二叉堆,并且有一些项的集合

*/

@SuppressWarnings("unchecked")

public BinaryHeap(AnyType[] items){

currentSize=items.length;

array=(AnyType[])new Comparable[(currentSize+2)*11/10];

int i=1;

for(AnyType item:items){

array[i++]=item;

}

buildHeap();

}

/*

* 进行排序

*/

private void buildHeap(){

for(int i=currentSize/2;i>0;i--){

percolateDown(i);

}

}

/*

* 用于扩容的函数

*/

private void enlargeArray(int newSize){

@SuppressWarnings("unchecked")


AnyType[] newArray=(AnyType[])new Comparable[newSize];//这里我本来new了一个Object,发现报错,因为不能new泛型,我就改成接口了缺,通过了,可以解释吗
AnyType[] old=array;

if(old!=null){

for(int i=0;i<old.length;i++){

newArray[i]=old[i];

}

}

array=newArray;

}

/*

* 把第hole位置的元素,放到合适的位置

*/

private void percolateDown(int hole){

int child;

AnyType tmp=array[hole];//得到当前位置的值

for(;hole*2<=currentSize;hole=child){//如果当前节点还有左孩子的话

child=hole*2;//得到左孩子

//如果当前孩子不等于size则说明还有右孩子,就比较左右孩子的大小,找到小的孩子,可以上移

if(child!=currentSize&&array[child+1].compareTo(array[child])<0){

child++;

}

//如果当前小的那个孩子比当前值要小的话就上移,然后继续循环

if(array[child].compareTo(tmp)<0){

array[hole]=array[child];

}else {//如果当前值比小的那个值还要小的话,就把当前值存在这个地方就可以了

break;

}

}

array[hole]=tmp;

}

/*

* 插入数据

*/

public void insert(AnyType x){

if(currentSize==array.length-1)

enlargeArray(array.length*2+1);

int hole=++currentSize;

//把新插入的元素和最后一个节点的父亲节点比大小,如果比他小那个父亲节点就下移,

//一直到比他大,就把值插入当前位置。

for(array[0]=x;x.compareTo(array[hole/2])<0;hole/=2)

array[hole]=array[hole/2];

array[hole]=x;

}

/*

* 删除最小元

*/

public AnyType deleteMin(){

if(isEmpty()){

throw new UnsatisfiedLinkError();

}

AnyType minItem=findMin();//只要把根节点的值给他就好了,就是坐标为1的值

array[1]=array[currentSize--];//把最底端的值给第一个元素

percolateDown(1);//然后执行这个收入的插入

return minItem;

}

public boolean isEmpty(){

return currentSize==0;

}

private AnyType findMin(){

return array[1];

}
}

测试:
public static void main(String[] args) {
// TODO Auto-generated method stub
BinaryHeap<Integer> binaryHeap=new BinaryHeap<>();
binaryHeap.insert(1);
binaryHeap.insert(5);
binaryHeap.insert(4);
binaryHeap.insert(2);
binaryHeap.insert(7);
while(!binaryHeap.isEmpty()){
System.out.println(binaryHeap.deleteMin());
}
}效果:
1
2
4
5
7

标签:优先,队列,int,算法,child,AnyType,array,hole,currentSize
From: https://blog.51cto.com/u_12026373/5930816

相关文章

  • IIS 之 连接数、并发连接数、最大并发工作线程数、队列长度、最大工作进程数
    http://t.zoukankan.com/l1pe1-p-7742936.html一、IIS连接数一般购买过虚拟主机的朋友都熟悉购买时,会限制IIS连接数,顾名思义即为IIS服务器可以同时容纳客户请求的最......
  • 算法与数据结构实验四
    实验项目名称:实验四       一、 实验目的1)掌握图的邻接矩阵、邻接表存储结构表示及其创建算法2)掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法;3)掌握图......
  • 算法与数据结构实验五 查找
    实验项目名称:实验五    查找  一、 实验目的1.掌握散列表的建立2.掌握散列查找算法的实现。二、 实验内容6-2线性探测法的查找函数试实现线性探测法的查找函......
  • 算法与数据结构实验六 内部排序
    实验项目名称:实验六    内部排序 一、 实验目的1.掌握插入排序的方法及效率分析2.掌握选择排序的方法及效率分析3.掌握交换排序的方法及效率分析4.掌握归并排序的......
  • 卡尔曼滤波算法-通俗理解
    简单来说,卡尔曼滤波器是一个“optimalrecursivedataprocessingalgorithm(最优化自回归数据处理算法)”。对于解决很大部分的问题,他是最优,效率最高甚至是最有用的。他的广......
  • TIANCHI天池-OGeek算法挑战赛-完整方案及代码(亚军)
    首先很幸运拿到TIANCHI天池-OGeek算法挑战赛大赛的亚军,同时非常感谢大佬队友的带飞,同时希望我的分享与总结能给大家带来些许帮助,并且一起交流学习。(作者:王贺,知乎:鱼遇雨欲语......
  • 每日算法之把数组排成最小的数
    JZ45把数组排成最小的数描述输入一个非负整数数组numbers,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组[3,32,321],则打印出这三......
  • 第一章算法概述总结
    代码规范类及其排版格式声明属性依次序是public:、protected:、private:。关键字public,protected,private不要缩进,声明的函数和变量缩进一个制表符。类声明前应加上注释,注......
  • 常见数据结构与算法的Python实现
    有人问我数据结构与算法怎么学?怎么用Python实现常见的数据结构算法?我找到一个github标星66.6k+的仓库,把各种常见算法用Python实现了,而且还有动图演示,非常值得推荐。(黄海广)仓......
  • 推荐:常见算法的python实现(github上25000多star)
    近日在github上发现一个25000多star的仓库,把各种常见算法用python实现了,而且还有动图演示,非常值得推荐。仓库说明这个仓库用python语言实现了绝大部分算法,主要是用于教学目......