亲宝软件园·资讯

展开

Java 堆的应用

Pretend.. 人气:0

一、堆的创建

1、向下调整(以小堆为例)  

让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)

如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在:

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】使用的注意事项:

PriorityQueue的扩容方式:

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)
用一个集合来创建优先级队列

加载全部内容

相关教程
猜你喜欢
用户评论