Java 数据结构之堆的概念与应用
作者：文墨轩 发布时间：2023-11-24 05:36:18
java数据结构的堆
什么是堆
堆指的是使用数组保存完全二叉树结构，以层次遍历的方式放入数组中。
如图：
注意：堆方式适合于完全二叉树，对于非完全二叉树若使用堆则会造成空间的浪费
对于根节点与其左右孩子在数组中的下标关系可表示为:left=2parent+1,right=2parent+2,parent=(child-1)/2
堆的类型
对于堆来说一共有两种类型：一为大根堆，还有一个为小根堆
小根堆
小根堆指的是：所有的根结点的值小于左右孩子结点的值
如图：
大根堆
大根堆指的是：所有根结点的值大于左右孩子结点的值。
如图：
当使用堆进行从小到大进行排序时应该使用大堆进行排序
堆的基本操作：创建堆
以创建大堆为例：我们先给定一个数组，该数组在逻辑上可以视为一颗完全二叉树，但目前并不是堆，但我们可以通过一定的算法将其变化为堆，通常我们从倒数第一个结点进行调整，一直调整到根结点的数，这样就调整为堆了；
如示例：
//建堆前
int array[]={1,5,3,8,7,6};
//建堆后
int array[]={ 8,7,6,5,1,3 };
调整方式：
第一步：先将数组还原成一个完全二叉树
如图：
第二步：如果倒数第一个叶子结点有兄弟结点则先与兄弟结点比较大小然后再取大的结点与父结点比较大小，如果没有兄弟结点则直接与父结点比较大小，如果值比父结点值大则交换值，一直这样调整到根节点的树，就可以调整成堆。
操作如图：
其核心代码如下：
public static void shiftDown(int[] array,int parent){
int child=2*parent+1;
while (child<array.length){
if(child+1<array.length){
if (array[child]<array[child+1]){
child++;
}
}
if(array[child]>array[parent]){
int tmp=array[child];
array[child]=array[parent];
array[parent]=tmp;
parent=child;
child=parent*2+1;
}
else {
break;
}
}
}
public static void createHeap(int[] array){
for (int i = (array.length-1-1)/2; i >=0; i--) {
shiftDown(array,i);
}
}
public static void main(String[] args) {
int array[]={1,5,3,8,7,6};
createHeap(array);
System.out.println(Arrays.toString(array));
}
堆的时间复杂度和空间复杂度
建堆时没有使用额外的空间因此其空间复杂度为O(1);
注意：该函数shiftDown（int[] array,int parent)时间复杂度为O(logn),建堆的时间复杂度为O(n*logn),但是建堆的时间复杂度为O(n)其推导如下：
堆的应用-优先级队列
概念
我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象.一个简单的例子：一天晚上，你正在看电视，这时你的父母叫你去厨房帮忙，那么这时你应该处理最重要的事情：去厨房帮妈妈的忙在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
注意：实现优先级队列的方式有很多种，一般来说我们一般使用堆来构建优先级队列
优先级队列基本操作
入优先级队列
以大堆为例：
首先按尾插方式放入数组
比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
否则，交换其和双亲位置的值，重新进行 2、3 步骤
直到根结点
如图：
核心代码如下：
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];//先创建长度为10的数组
}
public boolean isFull() {
return this.usedSize == this.elem.length;
}
public void push(int val) {
//先判断队列是否已经满，如果以满则扩容
if (isFull()){
Arrays.copyOf(this.elem,this.elem.length*2);
}
this.elem[this.usedSize++]=val;
shiftUp(this.usedSize-1);
}
public void shiftUp(int child) {
int parent=(child-1)/2;
while (parent>=0){
if(this.elem[child]>this.elem[parent]){
int tmp=this.elem[child];
this.elem[child]=this.elem[parent];
this.elem[parent]=tmp;
child=parent;
parent=(child-1)/2;
}
else{
break;
}
}
}
}
出优先级队列首元素
注意：为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向
下调整方式重新调整成堆
核心代码如下：
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];//10个0
}
public boolean isFull() {
return this.usedSize == this.elem.length;
}
public boolean isEmpty() {
return this.usedSize == 0;
}
public int poll() {
//先判断队列是否为空，如果为空则抛出异常
if (isEmpty()){
throw new RuntimeException("优先级队列为空");
}
int tmp=this.elem[0];
this.elem[0]=this.elem[this.usedSize-1];
this.usedSize--;
shiftDown(0);
return tmp;
}
public void shiftDown(int parent) {
int child = 2*parent+1;
//进入这个循环 说明最起码你有左孩子
while (child < this.usedSize) {
//该条件进入是判断其是否有右兄弟
if(child+1 < this.usedSize &&
this.elem[child] < this.elem[child+1]) {
child++;
}
//child所保存的下标，就是左右孩子的最大值
if(this.elem[child] > this.elem[parent]) {
int tmp = this.elem[child];
this.elem[child] = this.elem[parent];
this.elem[parent] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;//如果孩子节点比父亲节点小 直接结束了
}
}
}
}
java的优先级队列
在java中，我们不必单独创建一个堆用于实现优先级对列
可以使用PriorityQueue
例如：
PriorityQueue<Integer> queue=new PriorityQueue<>();
java中的优先级对列其实是小堆若想使用大堆方法则需要从写比较方法
方法如下（方法不唯一）
PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator(Integer)){
public int compare(Integer o1,Integer o2){return o2-o1}
};
优先级的使用方法：
| 错误处理 | 抛出异常 | 返回特殊值 |
|---|---|---|
| 入队列 | add(e) | offer(e) |
| 出队列 | remove() | poll() |
| 队首元素 | element() | peek() |
堆的常见面试题
最后一块石头的重量
最后一块石头的重量题
解题思路：该题可以使用变化过的优先级队列进行解答，即将默认小堆的优先级队列改为大堆模式的优先级队列，则将每块石块的重量使用循环放入优先级队列中其自动会把最重的石块放入队首，而后，将队列的头两个元素依次取出记为max1,max2,并将sum=max1-max2;如果sum大于0则又放入队列中不是则继续重复上诉操作
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> queue = new PriorityQueue<>((i1, i2) -> i2 - i1);//改为大堆
for(int i=0;i<stones.length;i++){
queue.offer(stones[i]);
}
while(queue.size()>=2){
int max1=queue.poll();
int max2=queue.poll();
int sum=max1-max2;
if(sum>0){
queue.offer(sum);
}
}
if(queue.size()>0){
return queue.poll();
}
return 0;
}
}
找到K个最接近的元素
找到K个最接近的元素
题解主要思路：使用优先级队列，先判别k是否大于数组长度，大于则直接将数组存放到List，相反则先依次存放k个数，之后将想要存放到优先级队列中的数-x的绝对值记为sum1,队列中第一个元素-x的绝对值记为sum2，如果sum1小于sum2则将队列中第一个元素删除，将其他数放入队列中，最后将队列中元素存放到list中
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
PriorityQueue<Integer> queue=new PriorityQueue<>();
List<Integer> list=new ArrayList<>();
if(k>arr.length){
for (int num:arr) {
list.add(num);
}
}
else {
for (int i = 0; i < arr.length; i++) {
if(i<k){
queue.offer(arr[i]);
}
else {
int sum1=Math.abs(arr[i]-x);
int sum2=Math.abs(queue.peek()-x);
if(sum1<sum2){
queue.poll();
queue.offer(arr[i]);
}
}
}
while (!queue.isEmpty()){
list.add(queue.poll());
}
}
return list;
}
}
查找和最小的K对数字
查找和最小的K对数字
主体解题思路：使用优先级队列将其先改变为大堆模式，使用循环先存放k个元素，之后想要存入队列的元素与队头元素比较，如果比队头元素小则删除队头元素，存放该元素，相反则继续上诉操作最后放入数组中
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<List<Integer>> queue=new PriorityQueue<>(k,(o1,o2)->{
return o2.get(0)+o2.get(1)-o1.get(0)-o1.get(1);
});
for (int i=0;i<Math.min(nums1.length,k);i++)
{
for (int j = 0; j < Math.min(nums2.length, k); j++) {
List<Integer> list=new ArrayList<>();
if (queue.size()<k){
list.add(nums1[i]);
list.add(nums2[j]);
queue.offer(list);
}
else {
int tmp=queue.peek().get(0)+queue.peek().get(1);
if(nums1[i]+nums2[j]<tmp){
queue.poll();
list.add(nums1[i]);
list.add(nums2[j]);
queue.offer(list);
}
}
}
}
List<List<Integer>> list=new ArrayList<>();
for (int i = 0; i < k&&!queue.isEmpty(); i++) {
list.add(queue.poll());
}
return list;
}
}
来源：https://blog.csdn.net/weixin_49830664/article/details/120807877
0
投稿猜你喜欢
被kafka-client和springkafka版本坑上周刚刚欢天喜地的在linux上部了kafka，这周打算用spring-boot框架- 1.概述数据库开发一直是JAVA开发的核心之一，作为现在JAVA EE的基石框架，Spring Boot自身携带了一个JDBCTemplat
- 介绍超级管理员：系统管理、用户管理、网点管理、运输点管理、快递员管理、网点申请管理（审核）、报价管理（时效报价）等。普通用户：注册登录、个人
- 1 配置多数据源时，application.yml 的有关mybatis的配置是失效的，因为他不知道配置哪一个数据源2 applicatio
- 多选和单选的不同之处单选的时候，选中一个就可以直接把结果返回，因此本身底部弹窗无需状态管理。但到多选的时候，需要知道当前选中的选项，有选项被
- 一、简介（1）、MySQL是一个关系型数据库系统,是如今互联网公司最常用的数据库和最广泛的数据库。为服务端数据库，能承受高并发的访问量。（2
- 本文主要探究的是关于Bean的作用域、生命周期的相关内容，具体如下。Bean的作用域Spring 3中为Bean定义了5中作用域，分别为si
- 概述LruCache的核心原理就是对LinkedHashMap的有效利用，它的内部存在一个LinkedHashMap成员变量，值得注意的4个
- 废话开篇：iOS与android在实现列表界面的时候是有重用机制的，目的就是减少内存开销，用时间换空间。个人感觉flutter并没有特别强调
- 摘要：想必大家做开发的时候都会用到下拉刷新的控件，现在各种第三方的下拉刷新控件不胜枚举。当然最NB的还是XListView。其他也有针对Gr
- Android的应用被限制为最多占用16m的内存，至少在T-Mobile G1上是这样的（当然现在已经有几百兆的内存可以用了——译者注）。它
- 本文实例为大家分享了java实现短信验证码5分钟有效时间，供大家参考，具体内容如下实现一个发送短信验证码的请求，要求5分钟之内重复请求，返回
- UI 妹纸又给了个图叫我做，我一看是这样的：我们首先把这个控件划分成 几个部分：1.底下部分的直线 ：2.左右两边的半圆
- 综述在Android系统中，出于对性能优化的考虑，对于Android的UI操作并不是线程安全的。也就是说若是有多个线程来操作UI组件，就会有
- 前言在电商的应用中，最常见的就是在首页或完成某事件之后，弹出一堆的活动/广告。假如重叠弹出，很丑，给用户的体验也不好，所以一般都会依次依条件
- Jackson反序列化遇到的问题最近在项目中需要使用Jackson把前台转来的字符转为对象，转换过程中发生了错误，报错如下com.faste
- mybatis-plus自动配置mapper.xml与java接口映射本来没有mybatis-plus的话，这个工作是通过mybatis-s
- — 遇到问题今天在IDEA里面运行项目的时候报了一个错，如下图所示：— 找到问题根源其实控制台给出的错误信息提示说的很明显：类加载器加载文件
- 在一个完整的项目中，如果每一个控制器的方法都返回不同的结果，那么对项目的维护和扩展都会很麻烦；并且现在主流的开发模式时前后端分离的模式，如果
- 一.以springboot为例,建立代码1.IExecCommandServer:public interface IExecCommand
