欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【Java】PriorityQueue 实现最大最小堆

程序员文章站 2024-01-03 20:59:22
PriorityQueue 实现最大最小堆什么是堆?堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:堆中某个节点的值总是不大于或不小于其父节点的值;堆总是一棵完全二叉树。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是在程序运行时,而不是在程序编译时,申请某个大小的内存空间。即动态分配内存,对其访问和对一般内存的访问没有区别。堆是应用程序在运行的时候请求操作系统分配给自己内存,一般是申请/给予的过程。...

PriorityQueue 实现最大最小堆

什么是堆?

堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;

  • 堆总是一棵完全二叉树。

  • 将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

  • 堆是在程序运行时,而不是在程序编译时,申请某个大小的内存空间。即动态分配内存,对其访问和对一般内存的访问没有区别。

  • 堆是应用程序在运行的时候请求操作系统分配给自己内存,一般是申请/给予的过程。

  • 堆是指程序运行时申请的动态内存,而栈只是指一种使用堆的方法(即先进后出)。

最大堆最最小堆画图理解

【Java】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

相关标签: 算法

上一篇:

下一篇: