Python 官方文档:入门教程 => 点击学习
目录一、堆的创建1、向下调整(以小堆为例) 2、创建堆3、创建堆的时间复杂度 二、堆的插入和删除1、堆的插入2、堆的删除 三、堆的应用1、堆排序2、t
让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)
如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在:
parent小于较小的孩子child,调整结束否则:交换parent与较小的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子树不满足堆的性质,因此需要继续向下调整,即parent = child;child = parent*2+1; 然后继续2。
public void shiftDown(int[] elem,int parent,int len){
int cur=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;
}
}
对于普通序列,我们需要从它的第一个有左节点的父节点开始调整,知道整棵树满足堆的性质。
堆必须是完全二叉树,满二叉树也是完全二叉树。由下面的计算,创建堆的时间复杂度为O(n).
【向上调整】
public void shiftUp(int elem[],int child){
int parent=(child-1)/2;
while(parent>=0){
if(elem[child]>elem[parent]){
swap(child,parent);
child=parent;
parent=(child-1)/2;
}else{
break;
}
}
}
根据堆的性质,对删除的一定是堆顶元素。步骤如下:
升序:创建大根堆
降序:创建小根堆
交换堆顶元素和堆得最后一个元素,进行向下调整,直到堆有序。
top-k问题:求数据集合中前k个大或者小的元素,一般数据量都比较大。
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] array=new int[k];
if(arr==null||arr.length<=k||k==0){
return array;
}
PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->b-a);
int i=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++;
}
int size=queue.size();
for(int j=0;j<size;++j){
array[j]=queue.poll();
}
return array;
}
}
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列。PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,本文主要介绍PriorityQueue。
【PriorityQueue】使用的注意事项:
PriorityQueue的扩容方式:
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
PriorityQueue采用了:Comparble和Comparator两种方式。
1. Comparble是默认的内部比较方式,如果用户插入自定义类型对象时,该类对象必须要实现Comparble接口,并覆写compareTo方法
2. 用户也可以选择使用比较器对象,如果用户插入自定义类型对象时,必须要提供一个比较器类,让该类实现Comparator接口并覆写compare方法
// 用户自己定义的比较器:直接实现Comparator接口,然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
构造器 | 功能介绍 |
PriorityQueue() | 创建一个空的优先级队列,默认容量是11 |
PriorityQueue(int initialCapacity) | 创建一个初始容量为initialCapacity的优先级队列,注意: initialCapacity不能小于1,否则会抛IllegalArgumentException异 常 |
PriorityQueue(Collection<? extends E> c) | 用一个集合来创建优先级队列 |
到此这篇关于Java 超详细讲解数据结构中的堆的应用的文章就介绍到这了,更多相关Java 堆的应用内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: Java 超详细讲解数据结构中的堆的应用
本文链接: https://www.lsjlt.com/news/144818.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0