-
2022-02-21 19:20:18
java使用优先队列实现大顶堆和小顶堆,默认是小根堆,当然记不住默认也没有关系
小根堆创建
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,(a,b) -> a-b);
大根堆创建
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,(a,b) -> b-a);
其中构造器中的k表示创建堆的大小,之后用Lambda表达式快速实现自定义排序
更多相关内容 -
java使用小根堆实现优先级队列的几种方式
2019-05-03 01:16:19NULL 博文链接:https://yunjiechao-163-com.iteye.com/blog/2405056 -
小根堆的Java实现
2021-03-13 19:50:18假设 i 为当前节点,那么 (i - 1) / 2 为父节点根据大小排序可分为小根堆和大根堆,小根堆即元素越小越在上方,大根堆则相反。这里注意:元素大小并不是按数组下标来排序的,下图的数字对应数组的坐标堆的应用:堆...1. 堆
堆是完全二叉树的数组形式,由于堆没有指针指向,所以可以利用下标来模拟指向,假设 i 为父节点,那么 2i+1 为左孩子,2i+2 为右孩子。假设 i 为当前节点,那么 (i - 1) / 2 为父节点
根据大小排序可分为小根堆和大根堆,小根堆即元素越小越在上方,大根堆则相反。这里注意:元素大小并不是按数组下标来排序的,下图的数字对应数组的坐标
堆的应用:
堆排序
优先级队列
快速找最值
2. 小根堆实现
内部操作有:
上浮:将小的元素往上移动、当插入元素时,将元素插入末尾,这样上移即可调整位置
下沉:将大的元素向下移动、当删除元素时,将首位交换,弹出尾部,首部下移即可调整位置
插入:添加元素
弹出:删除元素
主要是其插入弹出的思想,还有调整时注意下标,因为大小与下标相差1
package heap;
// 小根堆时间复杂度是O(1) ~ O(logn)
// 默认O(nlogn)
public class Heap {
// 实际存放元素个数
// 这里是个坑,debug了好久,起因:下标 = 实际大小-1
private int size;
// 数组存储元素
// 可以实现简单扩容,size++ > capacity时
// data = copyOf(data,capacity*2);
private int[] data = new int[10];
// 交换,传入下标
private void swap(int a, int b) {
int temp = data[a];
data[a] = data[b];
data[b] = temp;
}
// 较大的下沉
// 将当前节点与其较小儿子交换
// 并将更新当前节点为交换的儿子节点
public void fixDown(int index) {
int son = index * 2 + 1;
while (son <= size) {
if (son + 1 < size && data[son + 1] < data[son]) {
son++; // 这里这要比较左右孩子谁小
}
if (data[index] < data[son]) {
break; // 当前节点比孩子节点小,不用下沉退出循环
} else {
swap(index, son);
index = son;
son = index * 2 + 1;
}
}
}
// 较小的上浮
// 当前节点与父节点相比,若小于则交换,且将当前节点跟新为其父节点
public void fixUp(int index) {
int father = (index - 1) / 2;
while (father >= 0) {
// 这里卡死一次,debug后发现,只有一个元素会相等进入无限交换
if (data[index] >= data[father]) {
break; // 其父节点大于当前节点,不用上浮退出循环
} else {
swap(index, father);
index = father;
father = (index - 1) / 2;
}
}
}
// 插入
// 每次都在最后一个插入,然后上浮到合适位置
public Heap push(int value) {
data[size] = value;
fixUp(size++);
return this;
}
// 弹出根元素
// 让根元素和尾元素交换,让现在的根元素下沉即可
public int pop() {
swap(0, --size);
fixDown(0);
return data[size];
}
// 测试
public static void main(String[] args) {
Heap heap = new Heap();
// 乱序添加1~9
// 从输出也可以验证,元素大小并不是按数组小标来排序的
// 输出:123459786
heap.push(8).push(5).push(9)
.push(4).push(2).push(3)
.push(6).push(7).push(1);
while(heap.size > 0){
System.out.print(heap.pop());
}
}
}
-
Java实现小根堆和大根堆(PriorityQueue)
2020-06-28 08:23:011、小根堆实现 package test; import java.util.Comparator; import java.util.PriorityQueue; /* add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常 remove 移除并返回队列头部的元素 如果...Java里面的PriorityQueue底层默认使用的堆,所以我们使用PriorityQueue就能实现堆的功能。
1、小根堆实现
package test; import java.util.Comparator; import java.util.PriorityQueue; /* add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常 remove 移除并返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常 element 返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常 offer 添加一个元素并返回true 如果队列已满,则返回false poll 移除并返问队列头部的元素 如果队列为空,则返回null peek 返回队列头部的元素 如果队列为空,则返回null */ public class Test { public static void main(String[] args) { PriorityQueue<Integer>priorityQueue = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }); for(int i = 10; i >= 0; i--){ if(priorityQueue.size() < 5){ priorityQueue.add(i); }else { priorityQueue.remove(); priorityQueue.add(i); } } while (!priorityQueue.isEmpty()) { System.out.println(priorityQueue.remove()); } } }
2、大根堆
package test; import java.util.Comparator; import java.util.PriorityQueue; /* add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常 remove 移除并返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常 element 返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常 offer 添加一个元素并返回true 如果队列已满,则返回false poll 移除并返问队列头部的元素 如果队列为空,则返回null peek 返回队列头部的元素 如果队列为空,则返回null */ public class Test { public static void main(String[] args) { PriorityQueue<Integer>priorityQueue = new PriorityQueue<>(); for(int i = 0; i < 10; i++){ if(priorityQueue.size() < 5){ priorityQueue.add(i); }else { priorityQueue.remove(); priorityQueue.add(i); } } while (!priorityQueue.isEmpty()) { System.out.println(priorityQueue.remove()); } } }
-
堆排序(小根堆)的简单实现(java)
2022-04-09 15:53:21实现步骤: 1、构造堆; 2、得到堆顶元素,这个值就是最大值;...4、对堆进行调整,重新让除了最后一个元素的的剩余元素中的最大值放到堆顶; 5、重复2-4这个步骤,直到堆中剩一个元素为止 api设计: ...堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[1...n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素。
堆的定义如下:n个关键字序列L[1...n]称为堆,当且仅当该序列满足:
1、L(i)<=L(2i)且L(i)<=L(2i+1) 或
2、L(i)>=L(2i)且L(i)>=L(2i+1) (1<=i<=n/2)
满足第一种情况的称为小根堆(小顶堆,即最小的元素在根结点);
满足第二种情况的称为大根堆(大顶堆,即最大的元素在根结点)
实现步骤:
1、构造堆;
2、得到堆顶元素,这个值就是最大值;
3、交换堆顶元素和数组中的最后一个元素,此时所有元素中的最大元素已经被放到合适的位置
4、对堆进行调整,重新让除了最后一个元素的的剩余元素中的最大值放到堆顶;
5、重复2-4这个步骤,直到堆中剩一个元素为止
api设计:
实现代码
package com.yyy; public class HeapSort<T extends Comparable<T>> { //判断heap堆中索引i处的元素是否小于索引j处的元素 private static boolean less(Comparable[] heap, int i, int j) { return heap[i].compareTo(heap[j])<0; } //交换heap堆中i索引和j索引处的值 private static void exch(Comparable[] heap, int i, int j) { Comparable tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp; } //根据原数组source,构造出堆heap private static void createHeap(Comparable[] source, Comparable[] heap) { //把source中的元素拷贝到heap中,heap中的元素就形成一个无序的堆 System.arraycopy(source,0,heap,1,source.length); //对堆中的元素做下沉调整(从长度的一半处开始,往索引1处扫描) for (int i = (heap.length)/2;i>0;i--){ sink(heap,i,heap.length-1); } } //对source数组中的数据从小到大排序 public static void sort(Comparable[] source) { //构建堆 Comparable[] heap = new Comparable[source.length+1]; createHeap(source,heap); //定义一个变量,记录未排序的元素中最大的索引 int N = heap.length-1; //通过循环,交换1索引处的元素和排序的元素中最大的索引处的元素 while(N!=1){ //交换元素 exch(heap,1,N); //排序交换后最大元素所在的索引,让它不要参与堆的下沉调整 N--; //需要对索引1处的元素进行对的下沉调整 sink(heap,1, N); } //把heap中的数据复制到原数组source中 System.arraycopy(heap,1,source,0,source.length); } //在heap堆中,对target处的元素做下沉,范围是0~range private static void sink(Comparable[] heap, int target, int range){ while(2*target<=range){ //1.找出当前结点的较大的子结点 int max; if (2*target+1<=range){ if (less(heap,2*target,2*target+1)){ max = 2*target+1; }else{ max = 2*target; } }else{ max = 2*target; } //2.比较当前结点的值和较大子结点的值 if (!less(heap,target,max)){ break; } exch(heap,target,max); target = max; } } }
测试代码:
public static void main(String[] args) { //待排序数组 String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"}; //通过HeapSort对数组中的元素进行排序 HeapSort.sort(arr); //打印排序后数组中的元素 System.out.println(Arrays.toString(arr)); }
-
Java 中的大根堆和小根堆
2019-09-02 22:34:15小根堆和大根堆 **完全二叉树:**完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时... -
Java实现的小根堆
2019-01-11 10:50:45文章目录1、二叉堆2、一个例子2.1 生成完全二叉树:2.2、调整为小根堆2.3、插入元素2.4、取出堆顶元素2.5、Java代码3、画图工具 1、二叉堆 什么是二叉堆? 二叉堆本质上是一种完全二叉树,它分为两个类型: 1.... -
Java——PriorityQueue(优先队列)——小根堆和大根堆思想
2021-11-15 22:29:05Java的优先队列默认是小根堆 import java.util.PriorityQueue; public class Zz { public static void main(String[] args) throws Exception{ PriorityQueue<Integer>a=new PriorityQueue<>(); ... -
java实现关于小根堆的创建
2020-02-16 17:54:34创建小根堆的两种方法 上滑创建 可将单个的数插入到小根堆中 下滑创建 用于将一个顺序结构的二叉树数组创建为一个小根堆 package java数据结构练习; import java.util.Arrays; public class 小根堆 { static ... -
使用 Java 实现优先队列(小根堆)
2020-04-16 23:33:47使用 Java 实现优先队列优先队列基本模型优先队列的实现基于链表实现基于二叉查找树实现基于堆实现二叉堆(binary heap)开始实现一个支持泛型的优先队列属性插入一个元素建堆 优先队列基本模型 优先队列的基本模型... -
java使用PriorityQueue即优先队列实现大根堆和小根堆
2020-11-08 15:13:51java使用PriorityQueue即优先队列实现大根堆和小根堆 -
java堆排序算法(小根堆)
2016-12-30 20:33:10这几天学习堆排序算法,主要是引用老师的方法进行编写的,通过多线程和管道通信(即java的PipedInputStream和PipedOutputStream)来实现大量数据的排序 1、首先是将数据分割成nsorters(16、32、64、……)块,对每... -
Java实现堆排序(大根堆)的示例代码
2020-08-25 12:02:11主要介绍了Java实现堆排序(大根堆)的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧 -
栈、队列、小根堆和大根堆的Java API使用
2019-05-15 21:43:44下面对Java中的栈、队列、小根堆和大根堆做一个简单的介绍。 它们都有共用的collections接口中定义的常见函数isEmpty(),可以判断该数据结构中是否还有元素。 栈 Java中有Stack类,但现在已经过时了,不推荐使用。一... -
Java 堆排序(大根堆及小根堆)
2017-12-21 16:24:36整理网上的最大堆及最小堆代码public abstract class Sorter { public abstract void sort(int[] array); }public class HeapSorter extends Sorter { @Override public void sort(int[] array) { heapSort(arr -
用PriorityQueue类构造大根堆和小根堆-Java
2021-01-05 18:19:241、大顶堆:头部为堆中最大的值 2、小顶堆:头部为队中最小的值 ...构建小根堆。 PriorityQueue small=new PriorityQueue<>(); 构建大根堆。 PriorityQueue pq = new PriorityQueue((a, b) -> b - a); ... -
【Java集合框架】通过Queue创建小根堆和大根堆
2021-04-07 18:55:09PriorityQueue是Java中内置的数据结构,表示堆。 PriorityQueue类继承于抽象类AbstractQueue,而AbstractQueue类实现了Queue... // 默认为小根堆 Queue<Integer> a = new PriorityQueue<>(); System -
小根堆(Heap)的详细实现
2021-05-24 04:53:41堆的介绍Heap是一种数据结构具有以下的特点:1)完全二叉树2)heap中存储的值是偏序Min-heap: 父节点的值小于或等于子节点的值Max-heap: 父节点的值大于或等于子节点的值堆的存储一般都用数组来表示堆,i结点的父结点... -
Java实现最小堆
2020-08-01 17:01:37在最小堆中,它首先是一颗完全二叉树,并且根节点的值,要比左右孩子的值都要小,同时,左右子树也是最小堆。本文包含堆的操作如下: (1)插入一个节点 (2)删除堆顶元素,也就是删除最小值 (3)通过给定的一... -
堆排序-以小根堆为例
2020-09-29 10:57:49提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录前言一、什么是堆二、堆排序过程1.创建堆2.堆排序总结前言一、pandas是什么?二、使用步骤1....下面将以小根堆(就是下层比 -
数据结构java版之堆
2022-01-26 21:16:11二、堆 1.概念 2.建堆 3.向下调整 三、堆的应用(优先级队列) 1.概念 2.内部原理 3.操作 ①入队列 ②出队列(优先级最高) ③返回队首元素(优先级最高) 4. 堆的其他应用-TopK 问题 一、二叉树的顺序... -
java借助PriorityQueue实现小根堆和大根堆
2018-05-16 13:58:40根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆。借助类PriorityQueue 可以实现小根堆和大根堆。对于... -
小根堆创建,插入,删除,排序等操作图解
2020-03-28 11:50:46堆:是用数组实现的完全二叉树,没有使用指针,根据数组的下标进行构建堆 ...小根堆的根节点数据是最小的数据,每个节点的数据都比其子节点小 注意:堆的根节点中存放的是最大或者最小元素,但是... -
Java最小堆解决TopK问题
2013-03-18 17:04:24Heapify(int i):当元素i的左右子树都是小根堆时,通过Heapify让i元素下降到适当的位置,以符合堆的性质。 回到上面的取TopK问题上,用最小堆的解决方法就是:先去源数据中的K个元素放到一个长度为K的数组... -
Java面试题之小根堆Heap
2018-03-14 16:42:30Java面试题之小根堆Heap: file.txt中有十亿个数字(每行一个),请用Java实现计算选出这些数中最大的100个 思路: 用前100个数字构建一个容量为100的小根堆; 继续读入数字,如果大于小根堆中最小的元素,就... -
Java堆排序
2022-02-05 23:54:50小顶堆:每个结点的值都小于或等于左右子结点的值 堆排序 堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是... -
Java~大根堆的创建以及实现堆的插入删除操作
2022-03-24 22:24:11目录 堆的概念以及问题思考 初始化堆并将其调整为大根堆 初始化堆 调整堆为大根堆 大根堆的插入和删除 ...大根堆的插入 ...大根堆的删除 ...堆的概念以及问题思考 ...= K2i+2)i = 0,1,2.....,则称为小... -
大根堆Java实现
2022-03-26 11:41:12import java.util.Arrays; // 大根堆建立 // 核心方法:heapInsert和heapify /** * 插入元素时候:堆上升 * 删除元素时候:堆下沉 * 堆排序和删除相关 */ public class BigHeap{ // 大根堆 private int[] heap;... -
Java实现最小堆一
2016-06-30 23:09:00Java实现最小堆一 堆是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)其左孩子和右孩子节点的值。 最大堆和最小堆是 二叉堆 的两种形式。 最大堆 : 根 结点的键值是所有...