Java堆的应用场景和实现方法介绍

胖强大大_9934

胖强大大_9934

2023-04-24

1912人浏览

转载

一、堆的创建

1、向下调整(以小堆为例)  

让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)

如果parent的左孩子存在,即:child

  • parent右孩子是否存在,存在找到左右孩子中最小的孩子,让child进行标记

  • 将parent与较小的孩子child比较,如果:

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><h4>2、创建堆</h4>
<p>对于普通序列,我们需要从它的第一个有左节点的父节点开始调整,知道整棵树满足堆的性质。</p>
<p><img src="https://img.php.cn/upload/article/000/000/164/168229609764061.png?x-oss-process=image/resize,p_40" alt="Java数据结构中的堆怎么应用"></p>
<h4>3、创建堆的时间复杂度</h4>
<p>堆必须是完全二叉树,满二叉树也是完全二叉树。由下面的计算,创建堆的时间复杂度为O(n).</p>
<p><img src="https://img.php.cn/upload/article/000/000/164/168229609796583.png?x-oss-process=image/resize,p_40" alt="Java数据结构中的堆怎么应用"></p>
<h3> 二、堆的插入和删除</h3>
<h4>1、堆的插入</h4>
<ul class=" list-paddingleft-2">
<li><p>将要插入的元素放在堆的最后,如果放不了,进行扩容</p></li>
<li><p>将新插入的节点向上调整,直到满足堆的性质</p></li>
</ul>
<p><img src="https://img.php.cn/upload/article/000/000/164/168229609735705.png?x-oss-process=image/resize,p_40" alt="Java数据结构中的堆怎么应用"></p>
<p> 【向上调整】</p>
<pre class="brush:java;">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;
            }
        }
    }

2、堆的删除

根据堆的性质,对删除的一定是堆顶元素。步骤如下:

  • 将堆顶元素和最后一个元素交换

  • 堆的元素个数减一

  • 对堆顶元素进行向下调整

Java数据结构中的堆怎么应用

 三、堆的应用

1、堆排序

升序:创建大根堆

降序:创建小根堆

FilePond 灵活的 JavaScript 文件上传库
FilePond 灵活的 JavaScript 文件上传库

FilePond 是一个 JavaScript 文件上传库,支持通过拖拽、粘贴和 API 方式处理文件、目录、URL 和 Data URI。它包含内置的图像优化功能、异步分块上传功能,并提供了适用于 React、Vue、Angular 和 Svelte 的适配器。

下载

交换堆顶元素和堆得最后一个元素,进行向下调整,直到堆有序。

Java数据结构中的堆怎么应用

2、top-k问题 【求最小的K个数】

top-k问题:求数据集合中前k个大或者小的元素,一般数据量都比较大。

Java数据结构中的堆怎么应用

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] array=new int[k];
        if(arr==null||arr.length queue=new PriorityQueue((a,b)->b-a);
        int i=0;
        for(;i<k><h3>四、常用接口的介绍</h3>
<h4>1、PriorityQueue的特性</h4>
<p>Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列。PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,本文主要介绍PriorityQueue。</p>
<p>【PriorityQueue】使用的注意事项:</p>
<ul class=" list-paddingleft-2">
<li><p>必须导入PeioriryQueue的包;</p></li>
<li><p>放置的元素必须是能够比较大小的,否则会抛出ClassCastException异常;</p></li>
<li><p>不能放置null元素,否则会抛出NullPointerException;</p></li>
<li><p>可以插入任意多的元素,内部会自动扩容;</p></li>
<li><p>底层使用了堆数据结构,默认是小堆。如果要构建大堆,则需要提供比较器。</p></li>
</ul>
<p>PriorityQueue的扩容方式:</p>
<ul class=" list-paddingleft-2">
<li><p>如果容量小于64时,是按照oldCapacity的2倍方式扩容的</p></li>
<li><p>如果容量大于等于64,是按照oldCapacity的1.5倍方式扩容的</p></li>
<li><p>如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容</p></li>
</ul>
<blockquote>int newCapacity = oldCapacity + ((oldCapacity > 1));</blockquote>
<p>PriorityQueue采用了:Comparble和Comparator两种方式。</p>
<p>1. Comparble是默认的内部比较方式,如果用户插入自定义类型对象时,该类对象必须要实现Comparble接口,并覆写compareTo方法</p>
<p>2. 用户也可以选择使用比较器对象,如果用户插入自定义类型对象时,必须要提供一个比较器类,让该类实现Comparator接口并覆写compare方法</p>
<pre class="brush:java;">// 用户自己定义的比较器:直接实现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());</integer></integer>

2、优先级队列的构造

构造器 功能介绍
PriorityQueue() 创建一个空的优先级队列,默认容量是11
PriorityQueue(int
initialCapacity)
创建一个初始容量为initialCapacity的优先级队列,注意:
initialCapacity不能小于1,否则会抛IllegalArgumentException异
常
PriorityQueue(Collection
extends E> c)
用一个集合来创建优先级队列

Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南

相关文章

java速学教程(入门到精通)
java速学教程(入门到精通)

java怎么学习?java怎么入门?java在哪学?java怎么学才快?不用担心,这里为大家提供了java速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

java

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
c语言中null和NULL的区别
c语言中null和NULL的区别

c语言中null和NULL的区别是:null是C语言中的一个宏定义,通常用来表示一个空指针,可以用于初始化指针变量,或者在条件语句中判断指针是否为空;NULL是C语言中的一个预定义常量,通常用来表示一个空值,用于表示一个空的指针、空的指针数组或者空的结构体指针。

2023.09.22

569

3

java中null的用法
java中null的用法

在Java中,null表示一个引用类型的变量不指向任何对象。可以将null赋值给任何引用类型的变量,包括类、接口、数组、字符串等。想了解更多null的相关内容,可以阅读本专题下面的文章。

2024.03.01

1698

6

string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.02

7839

3

int占多少字节
int占多少字节

int占4个字节,意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值,在某些情况下也可能是2个字节或8个字节,int是一种常用的数据类型,用于表示整数,需要根据具体情况选择合适的数据类型,以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.08.29

3705

6

c++怎么把double转成int
c++怎么把double转成int

本专题整合了 c++ double相关教程,阅读专题下面的文章了解更多详细内容。

2025.08.29

4908

10

C++中int的含义
C++中int的含义

本专题整合了C++中int相关内容,阅读专题下面的文章了解更多详细内容。

2025.08.29

3265

10

treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

3021

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
dev.java 官方:Learn Java
dev.java 官方:Learn Java

共0课时 | 0人学习

Java JDBC数据库连接官方教程
Java JDBC数据库连接官方教程

共0课时 | 0人学习