【Java】PriorityQueue 实现最大最小堆
程序员文章站
2024-01-03 20:59:22
PriorityQueue 实现最大最小堆什么是堆?堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:堆中某个节点的值总是不大于或不小于其父节点的值;堆总是一棵完全二叉树。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是在程序运行时,而不是在程序编译时,申请某个大小的内存空间。即动态分配内存,对其访问和对一般内存的访问没有区别。堆是应用程序在运行的时候请求操作系统分配给自己内存,一般是申请/给予的过程。...
PriorityQueue 实现最大最小堆
什么是堆?
堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:
-
堆中某个节点的值总是不大于或不小于其父节点的值;
-
堆总是一棵完全二叉树。
-
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
-
堆是在程序运行时,而不是在程序编译时,申请某个大小的内存空间。即动态分配内存,对其访问和对一般内存的访问没有区别。
-
堆是应用程序在运行的时候请求操作系统分配给自己内存,一般是申请/给予的过程。
-
堆是指程序运行时申请的动态内存,而栈只是指一种使用堆的方法(即先进后出)。
最大堆最最小堆画图理解
代码实现:
PriorityQueue:默认实现最小堆
public class Test {
public static void main(String[] args) {
int[] a = {2,17,4,12,8,21,15,33};
//1,默认实现的是最小堆,元素按照natural ordering排序(自然排序,例如,数字的从小到大)
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i : a) {
pq.offer(i);
}
while(!pq.isEmpty()) {
System.out.print(pq);
}
//输出(升序):[2, 8, 4, 17, 12, 21, 15, 33]
}
}
最大堆:
public class Test {
public static void main(String[] args) {
int[] a = {2,17,4,12,8,21,15,33};
//可以直接使用lamda表达式实现个人觉得这个方式比较好
PriorityQueue<Integer> pq =new PriorityQueue<>((a, b) -> b - a);
//2,通过比较器排序,实现最大堆
/* PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
// 以下是对比较器升序、降序的理解.
// (1) 写成return a.compareTo(b) 或者 return a-b表示升序
// (2) 写成return b.compareTo(a) 或者return b-a表示降序
return b.compareTo(a);
}
}) ;
*/
for (int i : a) {
pq.offer(i);
}
while(!pq.isEmpty()) {
System.out.print(pq);
}
//输出(降序):[33, 21, 17, 12, 8, 4, 15, 2]
}
}
.print(pq);
}
//输出(降序):[33, 21, 17, 12, 8, 4, 15, 2]
}
}
本文地址:https://blog.csdn.net/imbestman/article/details/111995273