Java 超详细讲解数据结构中的堆的应用

目录
  • 一、堆的创建
    • 1、向下调整(以小堆为例)
    • 2、创建堆
    • 3、创建堆的时间复杂度
  • 二、堆的插入和删除
    • 1、堆的插入
    • 2、堆的删除
  • 三、堆的应用
    • 1、堆排序
    • 2、top-k问题(求最小的K个数)
  • 四、常用接口的介绍
    • 1、PriorityQueue的特性
    • 2、优先级队列的构造

一、堆的创建

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。

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;
        }
    }

2、创建堆

对于普通序列,我们需要从它的第一个有左节点的父节点开始调整,知道整棵树满足堆的性质。

3、创建堆的时间复杂度

堆必须是完全二叉树,满二叉树也是完全二叉树。由下面的计算,创建堆的时间复杂度为O(n).

二、堆的插入和删除

1、堆的插入

  • 将要插入的元素放在堆的最后,如果放不了,进行扩容
  • 将新插入的节点向上调整,直到满足堆的性质

【向上调整】

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、堆的删除

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

  • 将堆顶元素和最后一个元素交换
  • 堆的元素个数减一
  • 对堆顶元素进行向下调整

三、堆的应用

1、堆排序

升序:创建大根堆

降序:创建小根堆

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

2、top-k问题(求最小的K个数)

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;
    }
}

四、常用接口的介绍

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方法即可
class IntCmp implements Comparator<Integer>{
   @Override
   public int compare(Integer o1, Integer o2) {
      return o2-o1;
   }
}
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());

2、优先级队列的构造

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

到此这篇关于Java 超详细讲解数据结构中的堆的应用的文章就介绍到这了,更多相关Java 堆的应用内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java 数据结构中栈结构应用的两个实例

    java 数据结构中栈结构应用的两个实例 1.单词逆序. 要求从控制台读入一串字符,按回车结束输入,同时显示其逆序字符串. 对于颠倒顺序的操作,用栈来解决是很方便的.具体思想是把字符串中的每一个字符按顺序存入栈中,然后再一个一个的从栈中取出.这时就是按照逆序取出的字符串. // reverse.java // stack used to reverse a string // to run this program: C>java ReverseApp import java.io.*; //

  • Java 超详细讲解数据结构的应用

    目录 一.bfs 二.双端队列 三.算法题 1.kotori和迷宫 2.小红找红点 3.小红玩数组  一.bfs bfs(广度优先搜索),类似二叉树的层序遍历,利用队列完成.一般用于求最短路. 图的最短路问题: 给定一个无向图,每条边的长度都是1.求1号点到x号点的最短距离. 顶点数n  边数为m q次询问  输入x 输出1到x的最短距离. 若1号点到x不连通,则输出-1 二.双端队列 双端队列的应用(区间翻转): 对于长度为n的数组,给定一个长度为m的区间,区间初始位置为a[1]到a[m].

  • java数据结构关于栈的实例应用

    此文章介绍关于顺序栈,链式栈的实例操作,括号匹配,表达式求值(后缀表达式) 1.声明一个栈接口SStack package ch05; public interface SStack <T>{ boolean isEmpty(); // 判断栈是否为空 void push(T x); // 元素x入栈 T pop(); // 出栈,返回栈顶元素 T peek(); // 返回栈顶元素,但不出栈 }  2. 定义顺序栈类SeqStack<T>,包括数据元素的对象数组和栈顶元素下标两个

  • Java 数据结构之堆的概念与应用

    目录 什么是堆 堆的类型 小根堆 大根堆 堆的基本操作:创建堆 堆的时间复杂度和空间复杂度 堆的应用-优先级队列 概念 优先级队列基本操作 入优先级队列 出优先级队列首元素 java的优先级队列 堆的常见面试题 最后一块石头的重量 找到K个最接近的元素 查找和最小的K对数字 java数据结构的堆 什么是堆 堆指的是使用数组保存完全二叉树结构,以层次遍历的方式放入数组中. 如图: 注意:堆方式适合于完全二叉树,对于非完全二叉树若使用堆则会造成空间的浪费 对于根节点与其左右孩子在数组中的下标关系可表

  • Java 超详细讲解数据结构中的堆的应用

    目录 一.堆的创建 1.向下调整(以小堆为例) 2.创建堆 3.创建堆的时间复杂度 二.堆的插入和删除 1.堆的插入 2.堆的删除 三.堆的应用 1.堆排序 2.top-k问题 [求最小的K个数] 四.常用接口的介绍 1.PriorityQueue的特性 2.优先级队列的构造 一.堆的创建 1.向下调整(以小堆为例) 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子) 如果parent的左孩子存在,即:child < size,

  • Java 超详细讲解数据结构中的堆的应用

    目录 一.堆的创建 1.向下调整(以小堆为例) 2.创建堆 3.创建堆的时间复杂度 二.堆的插入和删除 1.堆的插入 2.堆的删除 三.堆的应用 1.堆排序 2.top-k问题(求最小的K个数) 四.常用接口的介绍 1.PriorityQueue的特性 2.优先级队列的构造 一.堆的创建 1.向下调整(以小堆为例) 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子) 如果parent的左孩子存在,即:child < size, 进

  • C语言超详细讲解数据结构中双向带头循环链表

    目录 一.概念 二.必备工作 2.1.创建双向链表结构 2.2.初始化链表 2.3.动态申请节点 2.4.打印链表 2.5.销毁链表 三.主要功能 3.1.在pos节点前插入数据 尾插 头插 3.2.删除pos处节点数据 尾删 头删 3.3.查找数据 四.总代码 List.h 文件 List.c 文件 Test.c 文件 五.拓展 一.概念 前文我们已经学习了单向链表,并通过oj题目深入了解了带头节点的链表以及带环链表,来画张图总体回顾下: 在我们学习的链表中,其实总共有8种,都是单双向和带不带

  • C语言超详细讲解数据结构中的线性表

    目录 前言 一.分文件编写 1.分文件编写概念 2.代码展示 二.动态分布内存malloc 1.初识malloc 2.使用方法 三.创建链表并进行增删操作 1.初始化链表 2.在链表中增加数据 3.删除链表中指定位置数据 四.代码展示与运行效果 1.代码展示 2.运行效果 总结 前言 计算机专业都逃不了数据结构这门课,而这门课无疑比较难理解,所以结合我所学知识,我准备对顺序表做一个详细的解答,为了避免代码过长,采用分文件编写的形式,不仅可以让代码干净利落还能提高代码可读性,先解释部分代码的含义,

  • Java超详细讲解SpringMVC如何获取请求数据

    目录 1.获得请求参数 1)基本类型参数:​​​​​​​   2)POJO类型参数: 3)数组类型参数   4)集合类型参数   2.请求乱码问题 3.参数绑注解@RequestParam​​​​​​​ 4.获得Restful风格的参数 5.自定义类型转换器 6.获得请求头 7.文件上传 8.小结 1.获得请求参数 客户端请求参数的格式是:name=value&name=value- - 服务器端要获得请求的参数,有时还需要进行数据的封装,SpringMVC可以接收如下类型的参数: 1)基本类型

  • Java 超详细讲解十大排序算法面试无忧

    目录 排序算法的稳定性: 一.选择排序 二.冒泡排序 三.插入排序 四.希尔排序 五.堆排序 六.归并排序 七.快速排序 八.鸽巢排序 九.计数排序 十.基数排序 排序算法的稳定性: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,如果排序以后,保证这些记录的相对次序保持不变,即在原序列中,a[i]=a[j],且 a[i] 在 a[j] 之前,排序后保证 a[i] 仍在 a[j] 之前,则称这种排序算法是稳定的:否则称为不稳定的. 一.选择排序 每次从待排序的元素中选择最小的元素,依次

  • Java超详细讲解类变量和类方法

    目录 1.static静态变量 2.类变量(静态变量的访问) 3.类方法 1.static静态变量 1.静态变量被同一个类的所有对象共享 2.static类变量在类加载的时候就生成使用 static保存在class实例的尾部,在堆中 3.和C语言C++有点像 package com.demo.static_; import java.sql.SQLOutput; public class childgeme { public static void main(String[] args) { C

  • Java超详细讲解排序二叉树

    目录 排序二叉树概念 排序二叉树类的定义 添加节点 中序遍历 查找节点 查找某一节点的父节点 删除节点 排序二叉树概念 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树.是数据结构中的一类. 对于二叉排序树的任何一个非叶子节点, 要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大. 对二叉排序树进行中序遍历,结果就是按从小到大排序的. 排序二叉树类的定义 public class binarySortTree {

  • Java 超详细讲解IO操作字节流与字符流

    目录 IO操作 字节流 FileInputStream FileOutputStream 字节流读写案例 字符流 FileReader FileWriter 字节流与字符流的区别 IO操作 字节流 java.io.InputStream 输入流,主要是用来读取文件内容的. java.io.OutputStream 输出流,主要是用来将内容字节写入文件的. FileInputStream 该流用于从文件读取数据,它的对象可以用关键字 new 来创建. 有多种构造方法可用来创建对象. 可以使用字符串

  • Java 超详细讲解类的定义方式和对象的实例化

    目录 1.面对对象的初步认识 1.1什么是面向对象 1.2面向对象与面向过程 2.类的定义与使用 2.1简单认识类 2.2 类的定义格式 3.类的实例化 3.1什么是实例化? 3.2重点笔记 总结 1.面对对象的初步认识 1.1什么是面向对象 用面向对象的思想来涉及程序,更符合人们对事物的认知,对于大型程序的设计.扩展以及维护都非常友好. 1.2面向对象与面向过程 举一个买手机的例子 以面向对象的方式来处理买手机这件事的话,我们就不需要关注买手机的过程,具体手机怎么买,如何到手,用户不用去关心,

随机推荐