Java中的大顶堆和小顶堆
最编程
2024-08-14 20:54:37
...
一、大顶堆和小顶堆的原理
1、大顶堆
- 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大顶堆。大根堆要求根节点的关键字既大于或等于左子树的关键字值,又大于或等于右子树的关键字值。
2、小顶堆
- 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者,称为小顶堆。小根堆要求根节点的关键字既小于或等于左子树的关键字值,又小于或等于右子树的关键字值。
3、大顶堆和小顶堆对比图
4、大顶推和小顶堆的实现
public class MaxHeap {
public static void main(String[] args) {
//原始数组内容
int i,size,data[]={0,5,6,10,8,3,2,19,9,11};
size=data.length;
System.out.print("原始数组:");
for(i=1;i<size;i++)
System.out.print("["+data[i]+"] ");
System.out.println("");
//建立堆积树
MaxHeap.heap(data,size);
}
public static void heap(int data[] ,int size)
{
int i,j,tmp;
//建立堆积树节点
for(i=(size/2);i>0;i--)
MaxHeap.ad_heap(data,i,size-1);
System.out.print("\n堆积内容:");
//原始堆积树内容
for(i=1;i<size;i++)
System.out.print("["+data[i]+"] ");
}
public static void ad_heap(int data[],int i,int size){
int j,tmp,post;
j=2*i;
tmp=data[i];
post=0;
while(j<=size && post==0)
{
if(j<size)
{
//小顶堆的比较
//if(data[j]>data[j+1])
//找出两个子节点最大值
if(data[j]<data[j+1])
j++;
}
//小顶堆的比较
//if(tmp<=data[j])
//若树根较大,结束比较过程
if(tmp>=data[j]) {
post=1;
} else {
//若树根较小,则继续比较,这里将最大子节点赋值给父节点
data[j/2]=data[j];
j=2*j;
}
}
//指定树根为父节点
data[j/2]=tmp;
}
}
二、小顶堆的应用
1、求最大的k个数
- 1、求10亿个数中的最大的前10个数,时时构建只有10个元素的小顶堆,如果比堆顶小,则不处理;如果比堆顶大,则替换堆顶,然后依次下沉到适当的位置。 详细讲解请看公众号:码农有道
- 2、选择最大的K个数
public class findTopK {
//用PriorityQueue默认是自然顺序排序,要选择最大的k个数,构造小顶堆,每次取数组中剩余数与堆顶的元素进行比较,如果新数比堆顶元素大,则删除堆顶元素,并添加这个新数到堆中。
//找出前k个最大数,采用小顶堆实现
public static int[] findKMax(int[] nums, int k) {
//队列默认自然顺序排列,小顶堆,不必重写compare
PriorityQueue<Integer> pq = new PriorityQueue<>(k);
for (int num : nums) {
if (pq.size() < k) {
pq.offer(num);
//如果堆顶元素 < 新数,则删除堆顶,加入新数入堆
} else if (pq.peek() < num) {
pq.poll();
pq.offer(num);
}
}
int[] result = new int[k];
for (int i = 0; i < k&&!pq.isEmpty(); i++) {
result[i] = pq.poll();
}
return result;
}
public static void main(String[] args) {
int[]arr=new int[]{1, 6, 2, 3, 5, 4, 8, 7, 9};
System.out.println(Arrays.toString(findKMax( arr,5)));
}
}
2、数组中的第K个最大元素
// 小顶堆
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int val : nums) {
pq.add(val);
// 维护堆的大小为 K
if (pq.size() > k) {
//弹出最顶端的数,并删除
pq.poll();
}
}
//取最顶端的数
return pq.peek();
}
三、大顶堆的应用
-
PriorityQueue通过传入自定义的compara函数可以实现大顶堆
1、要选择最小的K个数使用大顶堆,每次取数组中剩余数与堆顶的元素进行比较,如果新数比堆顶元素小,则删除堆顶元素,并添加这个新数到堆中。
public static int[] findKMin(int[] nums,int k ){
PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int num:nums){
if (pq.size() <k){
pq.offer(num);
//如果堆顶元素 > 新数,则删除堆顶,加入新数入堆
}else if(pq.peek() > num){
pq.poll();
pq.offer(num);
}
}
int[] result = new int[k];
for (int i = 0;i<k&&!pq.isEmpty();i++){
result[i] = pq.poll();
}
return result;
}
public static void main(String[] args) {
int[]arr=new int[]{1, 6, 2, 3, 5, 4, 8, 7, 9};
System.out.println(Arrays.toString(findKMin( arr,5)));
}
2、数组中的第K个最小元素
public static int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int val : nums) {
pq.add(val);
// 维护堆的大小为 K
if (pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}