Java数据结构中的堆怎么应用
Java数据结构中的堆怎么应用
本篇内容介绍了“Java数据结构中的堆怎么应用”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
一、堆的创建
1、向下调整(以小堆为例)
让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)
如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在:
parent右孩子是否存在,存在找到左右孩子中最小的孩子,让child进行标记
将parent与较小的孩子child比较,如果:
parent小于较小的孩子child,调整结束否则:交换parent与较小的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子树不满足堆的性质,因此需要继续向下调整,即parent = child;child = parent*2+1; 然后继续2。
publicvoidshiftDown(int[]elem,intparent,intlen){intcur=parent*2+1;while(cur<len){if(cur+1<len){if(elem[cur+1]<elem[cur]){cur++;}}if(this.elem[cur]<this.elem[parent]){swap(cur,parent);}parent=cur;cur=parent*2+1;}}
2、创建堆
对于普通序列,我们需要从它的第一个有左节点的父节点开始调整,知道整棵树满足堆的性质。
3、创建堆的时间复杂度
堆必须是完全二叉树,满二叉树也是完全二叉树。由下面的计算,创建堆的时间复杂度为O(n).
二、堆的插入和删除
1、堆的插入
将要插入的元素放在堆的最后,如果放不了,进行扩容
将新插入的节点向上调整,直到满足堆的性质
【向上调整】
publicvoidshiftUp(intelem[],intchild){intparent=(child-1)/2;while(parent>=0){if(elem[child]>elem[parent]){swap(child,parent);child=parent;parent=(child-1)/2;}else{break;}}}
2、堆的删除
根据堆的性质,对删除的一定是堆顶元素。步骤如下:
将堆顶元素和最后一个元素交换
堆的元素个数减一
对堆顶元素进行向下调整
三、堆的应用
1、堆排序
升序:创建大根堆
降序:创建小根堆
交换堆顶元素和堆得最后一个元素,进行向下调整,直到堆有序。
2、top-k问题【求最小的K个数】
top-k问题:求数据集合中前k个大或者小的元素,一般数据量都比较大。
classSolution{publicint[]smallestK(int[]arr,intk){int[]array=newint[k];if(arr==null||arr.length<=k||k==0){returnarray;}PriorityQueue<Integer>queue=newPriorityQueue<>((a,b)->b-a);inti=0;for(;i<k;++i){queue.offer(arr[i]);}while(i<arr.length){if(arr[i]<queue.peek()){queue.poll();queue.offer(arr[i]);}i++;}intsize=queue.size();for(intj=0;j<size;++j){array[j]=queue.poll();}returnarray;}}
四、常用接口的介绍
1、PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列。PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,本文主要介绍PriorityQueue。
【PriorityQueue】使用的注意事项:
必须导入PeioriryQueue的包;
放置的元素必须是能够比较大小的,否则会抛出ClassCastException异常;
不能放置null元素,否则会抛出NullPointerException;
可以插入任意多的元素,内部会自动扩容;
底层使用了堆数据结构,默认是小堆。如果要构建大堆,则需要提供比较器。
PriorityQueue的扩容方式:
如果容量小于64时,是按照oldCapacity的2倍方式扩容的
如果容量大于等于64,是按照oldCapacity的1.5倍方式扩容的
如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
PriorityQueue采用了:Comparble和Comparator两种方式。
1. Comparble是默认的内部比较方式,如果用户插入自定义类型对象时,该类对象必须要实现Comparble接口,并覆写compareTo方法
2. 用户也可以选择使用比较器对象,如果用户插入自定义类型对象时,必须要提供一个比较器类,让该类实现Comparator接口并覆写compare方法
//用户自己定义的比较器:直接实现Comparator接口,然后重写该接口中的compare方法即可classIntCmpimplementsComparator<Integer>{@Overridepublicintcompare(Integero1,Integero2){returno2-o1;}}PriorityQueue<Integer>p=newPriorityQueue<>(newIntCmp());
2、优先级队列的构造
构造器 | 功能介绍 |
PriorityQueue() | 创建一个空的优先级队列,默认容量是11 |
PriorityQueue(int initialCapacity) | 创建一个初始容量为initialCapacity的优先级队列,注意: initialCapacity不能小于1,否则会抛IllegalArgumentException异 常 |
PriorityQueue(Collection<? extends E> c) | 用一个集合来创建优先级队列 |
“Java数据结构中的堆怎么应用”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注恰卡编程网网站,小编将为大家输出更多高质量的实用文章!