0


【JavaSE|数据结构】堆,优先级队列,topK问题与堆排序

⭐️前面的话⭐️

本篇文章带大家认识数据结构——堆,所谓的堆,其实就是使用顺序表实现的树,前面所介绍的二叉树是基于链式结构所实现的,本文将介绍底层为顺序表的二叉树,由于使用顺序表实现非完全二叉树会存在内存空间浪费问题,所以常常使用顺序表实现完全二叉树,而这个使用顺序表所实现的完全二叉树就是堆。

📒博客主页:未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创,CSDN首发!
📆首发时间:🌴2022年2月14日🌴
✉️坚持和努力一定能换来诗与远方!
💭参考书籍:📚《Java核心技术》,📚《Java编程思想》,📚《Effective Java》
💬参考在线编程网站:🌐牛客网🌐力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
🙏作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!


📌导航小助手📌


封面

题外话:在正式开始之前,我们先来看一看集合框架,画上√的表示博主已经介绍完毕了,可以翻看JavaSE系列专栏进行寻找,画上⭐️表示本文所介绍的内容。

0


1.堆

1.1什么是堆?

所谓堆,就是使用顺序表实现的完全二叉树 ,堆中的根结点的值大于所有非空子树结点的值,则该堆被称为大堆(大根堆),反之,堆中的根结点的值小于所有非空子树结点的值,则该堆被称为小堆(小根堆)。

例如下面这一个数组:
1-1
该数组对应的堆为:
1-2
大根堆:
1-3
小根堆:
1-4

1.2堆的创建

我们知道堆是由顺序表实现的,并且堆顶的元素大小大于(或小于)子堆的元素大小,堆的本质就是一棵完全二叉树,所以可以根据这个特点总结出堆是如何创建的。

  1. 找到堆中最后一个子树,该子树根结点不能为叶子结点。
  2. 对该子树进行向下方向的调整,若该堆为大根堆,找到该树两个子结点值较大的结点与根结点进行比较,如果这个子结点比根结点要,则先交换两结点的值,然后在堆的大小范围内,对被交换结点的子树作相同的调整,直到被调整的子树下标超出堆的大小或满足大堆条件,反之如果堆为小根堆,找到该树两个子结点值较小的结点与根结点进行比较,如果这个子结点比根结点要,则先交换两结点的值,然后在堆的大小范围内,对被交换结点的子树作相同的调整,直到被调整的子树下标超出堆的大小或满足小堆条件。
  3. 从最后一棵子树(该树不为叶子,最右边一棵高度为2的子树)开始,整棵树(以堆顶结点所代表的树)为结束,按此顺序对所有树进行向下调整,这个大(小)堆就创建好了。

不妨设最后一棵子树(非叶子)所对应数组下标为

parent

,其左子树根结点为

child

,堆大小为

len

,由于该树是一棵完全二叉树,所以下标会满足

    c
   
   
    h
   
   
    i
   
   
    l
   
   
    d
   
   
    =
   
   
    2
   
   
    ∗
   
   
    p
   
   
    a
   
   
    r
   
   
    e
   
   
    n
   
   
    t
   
   
    +
   
   
    1
   
   
    ;
   
   
    p
   
   
    a
   
   
    r
   
   
    e
   
   
    n
   
   
    t
   
   
    =
   
   
    (
   
   
    c
   
   
    h
   
   
    i
   
   
    l
   
   
    d
   
   
    −
   
   
    1
   
   
    )
   
   
    /
   
   
    2
   
  
  
   child=2*parent+1;parent=(child-1)/2
  
 
child=2∗parent+1;parent=(child−1)/2

最后一个结点下标为

    l
   
   
    e
   
   
    n
   
   
    −
   
   
    1
   
  
  
   len-1
  
 
len−1,父结点下标为

 
  
   
    (
   
   
    l
   
   
    e
   
   
    n
   
   
    −
   
   
    2
   
   
    )
   
   
    /
   
   
    2
   
  
  
   (len-2)/2
  
 
(len−2)/2。

对于向下调整中,以创建大根堆为例,如果一棵子树右结点存在且大于左结点的值,则

child++

指向右结点。
1-5
堆的结构:

publicclassHeap{privateint[] elem;privateint usedSize;publicHeap(){this.elem =newint[10];}//基本操作方法}

代码实现(Java):创建大根堆为例

/**
     *
     * @param arr 目标交换数组对象
     * @param index1 下标1
     * @param index2 下标2
     */privatevoidswap(int arr[],int index1,int index2){int tmp = arr[index1];
        arr[index1]= arr[index2];
        arr[index2]= tmp;}
/**
     * 向下调整
     * @param parent 父节点下标
     * @param len 堆大小
     */publicvoidshiftDown(int parent,int len){int child =2* parent +1;while(child < len){if(child +1< len &&this.elem[child]<this.elem[child +1]){
                child++;}if(this.elem[child]>this.elem[parent]){swap(this.elem, child, parent);
                parent = child;
                child =2* parent +1;}else{break;}}}
/**
     * 创建大根堆
     * @param data 堆中的数据
     */publicvoidcreatCopyBigHeap(int[] data){//拷贝数据for(int i =0; i < data.length; i++){if(isFull()){this.elem =Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[i]= data[i];
            usedSize++;}//从最后一棵完全二叉树子树开始调整int child =this.usedSize -1;int parent =(child -1)/2;while(parent >=0){shiftDown(parent, usedSize);
            parent--;}}//或者直接利用数组对象,不对它进行深拷贝publicvoidcreatBigHeap(int[] data){//拷贝数据this.elem = data;
        usedSize = data.length;//从最后一棵完全二叉树子树开始调整int child =this.usedSize -1;int parent =(child -1)/2;while(parent >=0){shiftDown(parent, usedSize);
            parent--;}}

建堆的时间复杂度为多少?

建堆的过程是自下而上的,堆的本质就是一棵完全二叉树,不妨设该二叉树的高度为

h

,堆元素个数为

n

,建堆时需要对所有高度大于1的子树进行调整,最坏情况下该堆是一个满堆,设该堆所处层次为

x

(从1开始),则第

x

层次的子树需要调整

h-x

次,有

     2
    
    
     
      h
     
     
      −
     
     
      1
     
    
   
  
  
   2^{h-1}
  
 
2h−1个结点,由于只调整高度大于1的子树,因此
x

的范围为

    [
   
   
    1
   
   
    ,
   
   
    h
   
   
    −
   
   
    1
   
   
    ]
   
  
  
   [1,h-1]
  
 
[1,h−1]。

设调整的次数为

    S
   
  
  
   S
  
 
S:

(1)

     S
    
    
     =
    
    
     
      2
     
     
      0
     
    
    
     ∗
    
    
     (
    
    
     h
    
    
     −
    
    
     1
    
    
     )
    
    
     +
    
    
     
      2
     
     
      1
     
    
    
     ∗
    
    
     (
    
    
     h
    
    
     −
    
    
     2
    
    
     )
    
    
     +
    
    
     .
    
    
     .
    
    
     .
    
    
     +
    
    
     
      2
     
     
      
       x
      
      
       −
      
      
       1
      
     
    
    
     ∗
    
    
     (
    
    
     h
    
    
     −
    
    
     x
    
    
     )
    
    
     +
    
    
     .
    
    
     .
    
    
     .
    
    
     +
    
    
     
      2
     
     
      
       h
      
      
       −
      
      
       2
      
     
    
    
     ∗
    
    
     1
    
   
   
    S=2^{0}*(h-1)+2^{1}*(h-2)+...+2^{x-1}*(h-x)+...+2^{h-2}*1
   
  
 S=20∗(h−1)+21∗(h−2)+...+2x−1∗(h−x)+...+2h−2∗1

由上述式子得特点可知S是通项公式为

    等
   
   
    比
   
   
    数
   
   
    列
   
   
    ∗
   
   
    等
   
   
    差
   
   
    数
   
   
    列
   
  
  
   等比数列*等差数列
  
 
等比数列∗等差数列的前n-1项和,对于该形式的通项公式和可以采用错位相减法,第一步乘以公比
2


(2)

     2
    
    
     S
    
    
     =
    
    
     
      2
     
     
      1
     
    
    
     ∗
    
    
     (
    
    
     h
    
    
     −
    
    
     1
    
    
     )
    
    
     +
    
    
     
      2
     
     
      2
     
    
    
     ∗
    
    
     (
    
    
     h
    
    
     −
    
    
     2
    
    
     )
    
    
     +
    
    
     .
    
    
     .
    
    
     .
    
    
     +
    
    
     
      2
     
     
      x
     
    
    
     ∗
    
    
     (
    
    
     h
    
    
     −
    
    
     x
    
    
     )
    
    
     +
    
    
     .
    
    
     .
    
    
     .
    
    
     +
    
    
     
      2
     
     
      
       h
      
      
       −
      
      
       1
      
     
    
    
     ∗
    
    
     1
    
   
   
    2S=2^{1}*(h-1)+2^{2}*(h-2)+...+2^{x}*(h-x)+...+2^{h-1}*1
   
  
 2S=21∗(h−1)+22∗(h−2)+...+2x∗(h−x)+...+2h−1∗1

(2)-(1)得:

     S
    
    
     =
    
    
     
      2
     
     
      1
     
    
    
     +
    
    
     
      2
     
     
      2
     
    
    
     +
    
    
     .
    
    
     .
    
    
     .
    
    
     +
    
    
     .
    
    
     .
    
    
     .
    
    
     +
    
    
     
      2
     
     
      
       h
      
      
       −
      
      
       2
      
     
    
    
     +
    
    
     
      2
     
     
      
       h
      
      
       −
      
      
       1
      
     
    
    
     −
    
    
     
      2
     
     
      0
     
    
    
     ∗
    
    
     (
    
    
     h
    
    
     −
    
    
     1
    
    
     )
    
   
   
    S=2^{1}+2^{2}+...+...+2^{h-2}+2^{h-1}-2^{0}*(h-1)
   
  
 S=21+22+...+...+2h−2+2h−1−20∗(h−1)

我们发现S为等比数列和减去

h-1

,等比数列求和公式为

     S
    
    
     n
    
   
   
    =
   
   
    
     a
    
    
     1
    
   
   
    (
   
   
    1
   
   
    −
   
   
    
     q
    
    
     n
    
   
   
    )
   
   
    /
   
   
    (
   
   
    1
   
   
    −
   
   
    q
   
   
    )
   
  
  
   S_n=a_1(1-q^n)/(1-q)
  
 
Sn​=a1​(1−qn)/(1−q)。

 
  
   
    
     S
    
    
     =
    
    
     2
    
    
     ∗
    
    
     (
    
    
     1
    
    
     −
    
    
     
      2
     
     
      
       h
      
      
       −
      
      
       1
      
     
    
    
     )
    
    
     /
    
    
     (
    
    
     −
    
    
     1
    
    
     )
    
    
     −
    
    
     h
    
    
     +
    
    
     1
    
   
   
    S=2*(1-2^{h-1})/(-1)-h+1
   
  
 S=2∗(1−2h−1)/(−1)−h+1

 
  
   
    
     S
    
    
     =
    
    
     
      2
     
     
      h
     
    
    
     −
    
    
     h
    
    
     −
    
    
     1
    
   
   
    S=2^h-h-1
   
  
 S=2h−h−1

完全二叉树中

    h
   
   
    =
   
   
    l
   
   
    o
   
   
    
     g
    
    
     2
    
   
   
    (
   
   
    n
   
   
    +
   
   
    1
   
   
    )
   
  
  
   h=log_2(n+1)
  
 
h=log2​(n+1)

 
  
   
    
     S
    
    
     =
    
    
     n
    
    
     +
    
    
     1
    
    
     −
    
    
     l
    
    
     o
    
    
     
      g
     
     
      2
     
    
    
     (
    
    
     n
    
    
     +
    
    
     1
    
    
     )
    
    
     −
    
    
     1
    
    
     =
    
    
     n
    
    
     −
    
    
     l
    
    
     o
    
    
     
      g
     
     
      2
     
    
    
     (
    
    
     n
    
    
     +
    
    
     1
    
    
     )
    
   
   
    S=n+1-log_2(n+1)-1=n-log_2(n+1)
   
  
 S=n+1−log2​(n+1)−1=n−log2​(n+1)

综上所述,建堆的时间复杂度为O(N)。

2.优先队列PriorityQueue

2.1优先队列

在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征,通常采用堆数据结构来实现。
比如说一个优先队列是由小根堆实现的,则该队列优先最小的元素出队,反之,优先队列由大根堆实现,则该队列优先最大的元素出队。

2.2PriorityQueue

在java中,PriorityQueue类就是优先队列,默认由小根堆实现,如果想要改变使用大根堆实现,则需要传入对象的比较器,或比较器内部类或lambda表达式所实现的比较器。

PriorityQueue构造方法:
方法类型作用public PriorityQueue()构造方法创建一个默认大小的优先队列(java8默认大小为11)public PriorityQueue(int initialCapacity)构造方法指定容量创建优先队列public PriorityQueue(Comparator<? super E> comparator)构造方法指定比较器创建一个默认大小的优先队列public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)构造方法指定比较器指定容量创建优先队列public PriorityQueue(Collection<? extends E> c)构造方法根据集合对象创建优先队列public PriorityQueue(PriorityQueue<? extends E> c)构造方法根据优先队列对象构造优先队列public PriorityQueue(SortedSet<? extends E> c构造方法根据SortedSet对象构造优先队列

importjava.util.Comparator;importjava.util.PriorityQueue;publicclassTest{publicstaticvoidmain(String[] args){PriorityQueue<Integer> priorityQueue1 =newPriorityQueue<>();//创建基于小根堆的优先队列
        priorityQueue1.offer(1);
        priorityQueue1.offer(2);
        priorityQueue1.offer(3);System.out.println(priorityQueue1);System.out.println("============");PriorityQueue<Integer> priorityQueue2 =newPriorityQueue<>(newComparator<Integer>(){@Overridepublicintcompare(Integer o1,Integer o2){return o1 - o2;}});//使用隐藏内部类创建基于小根堆的优先队列
        priorityQueue2.offer(1);
        priorityQueue2.offer(2);
        priorityQueue2.offer(3);System.out.println(priorityQueue2);System.out.println("============");PriorityQueue<Integer> priorityQueue3 =newPriorityQueue<>(newComparator<Integer>(){@Overridepublicintcompare(Integer o1,Integer o2){return o2 - o1;}});//使用隐藏内部类创建基于大根堆的优先队列
        priorityQueue3.offer(1);
        priorityQueue3.offer(2);
        priorityQueue3.offer(3);System.out.println(priorityQueue3);System.out.println("============");PriorityQueue<Integer> priorityQueue4 =newPriorityQueue<>((x, y)-> x-y);//使用lambda表达式创建基于小根堆的优先队列
        priorityQueue4.offer(1);
        priorityQueue4.offer(2);
        priorityQueue4.offer(3);System.out.println(priorityQueue4);System.out.println("============");PriorityQueue<Integer> priorityQueue5 =newPriorityQueue<>((x, y)-> y-x);//使用lambda表达式创建基于大根堆的优先队列
        priorityQueue5.offer(1);
        priorityQueue5.offer(2);
        priorityQueue5.offer(3);System.out.println(priorityQueue5);System.out.println("============");}}

上面的内部类与lambda先知道这么写,后续博文会介绍内部类与lambda表达式。
2-2

PriorityQueue基本操作方法:
作用遇到错误抛异常遇到错误返回特殊值入队public boolean add(E e)public boolean offer(E e)出队public boolean remove(Object o)public E poll()获取优先级最高的元素public E element()public E peek()
PriorityQueue其他常用方法:
方法类型作用public boolean contains(Object o)普通方法判断优先队列中是否包含对象opublic Object[] toArray()普通方法优先队列转数组public int size()普通方法获取优先队列元素个数public void clear()普通方法清空优先队列

2.3简单实现优先队列的基本操作

优先队列是基于堆实现的,本次使用大根堆来实现入队,出队,获取队头元素等基本操作。

入队:
步骤:

  1. 将元素放入堆尾。
  2. 对堆尾的结点进行向上方向调整,因为入队一个元素后,堆中只有一条到新插入结点路径上不是大根堆,所以仅需对该结点进行向上调整,所谓向上调整就是比较调整结点与父亲结点值的大小,以大根堆为例,如果该结点值比较大,则与父亲结点交换值,否则不需调整,该堆已经满足大根堆条件,因为交换后不知道上面的子树是否为大根堆,所以需要对交换路径上所有的结点进行相同的向上调整,直到调整完堆顶,过程中出现父亲结点比较大则结束调整,反之如果是小根堆,就把调整结点与父亲结点的比较方式改变一下即可。
  3. 入队完成。

堆的结构:

publicclassHeap{privateint[] elem;privateint usedSize;publicHeap(){this.elem =newint[10];}/**
     *
     * @param arr 目标交换数组对象
     * @param index1 下标1
     * @param index2 下标2
     */privatevoidswap(int arr[],int index1,int index2){int tmp = arr[index1];
        arr[index1]= arr[index2];
        arr[index2]= tmp;}//基本操作方法}

代码实现(基于大根堆):

//判断队列是否满或空publicbooleanisFull(){returnthis.elem.length ==this.usedSize;}publicbooleanidEmpty(){returnthis.usedSize ==0;}
//向上调整privatevoidshiftUp(int child){int parent =(child -1)/2;while(child >0){if(this.elem[parent]<this.elem[child]){swap(this.elem, parent, child);
                child = parent;
                parent =(child -1)/2;}else{break;}}}
/**
     * 基于大堆的优先队列进队
     */publicvoidoffer(int val){if(isFull()){this.elem =Arrays.copyOf(this.elem,2*this.elem.length);}//1.将元素插入堆尾this.elem[usedSize++]= val;//2.重新调整为大堆:向上调整shiftUp(usedSize -1);}

出队:
步骤:

  1. 将堆顶元素与堆尾元素交换,保存并删除堆尾元素。
  2. 对堆顶元素向下调整,因为堆顶交换元素的路径可能会破坏大根堆(或小根堆)。
  3. 返回之前保存的堆尾元素,即原优先队列队头元素。

实现代码(基于大根堆):

/**
     * 基于大堆的优先队列出队
     * @return 堆顶元素
     */publicintpoll(){if(idEmpty()){thrownewRuntimeException("优先队列为空!");}//1.将堆顶元素与堆尾元素交换swap(this.elem,0, usedSize -1);//2.保存原堆顶元素的值,并删除堆中原堆顶元素的值int ret =this.elem[--usedSize];//3.调整堆顶为根结点的树,使其调整为大堆shiftDown(0, usedSize);return ret;}

获取队头元素:
会出队,那获取队头元素就不在话下了。
实现代码:

/**
     * 获取优先队列(基于大堆)队头元素
     * @return 堆顶元素
     */publicintpeek(){if(idEmpty()){thrownewRuntimeException("优先队列为空!");}returnthis.elem[0];}

2.4堆排序

如果是基于升序排序,则使用大堆,基于降序排序,则使用小堆。
升序排序步骤:

  1. 将数组转换成大根堆,使用索引end标记最后一个元素。
  2. 将堆顶元素与end处元素交换,end--
  3. 对堆顶结点进行向下调整,调整的结点下标不大于end
  4. 重复2,3步骤,直到end<=0

简单说,因为大根堆堆顶存放最大元素,每次将最大元素与

end

出元素交换,再调整

end-1

部分的堆,这样就能依次把最大的元素放在后面,降序排列使用小根堆也是这个道理。
例如对下面这一个数组进行升序排序:
2-4-1
转成大堆:
2-4-2
排序过程图解:
红色表示堆顶元素与end索引出元素交换。
蓝色表示已经排好序了。
黄色表示向下调整。
2-4-3
2-4-4
排序后数组为:
2-4-5

堆的结构:

publicclassHeap{privateint[] elem;privateint usedSize;publicHeap(){this.elem =newint[10];}/**
     *
     * @param arr 目标交换数组对象
     * @param index1 下标1
     * @param index2 下标2
     */privatevoidswap(int arr[],int index1,int index2){int tmp = arr[index1];
        arr[index1]= arr[index2];
        arr[index2]= tmp;}publicvoidcreatBigHeap(int[] data){//拷贝数据this.elem = data;
        usedSize = data.length;//从最后一棵完全二叉树子树开始调整int child =this.usedSize -1;int parent =(child -1)/2;while(parent >=0){shiftDown(parent, usedSize);
            parent--;}}/**
     * 向下调整
     * @param parent 父节点下标
     * @param len 堆大小
     */publicvoidshiftDown(int parent,int len){int child =2* parent +1;while(child < len){if(child +1< len &&this.elem[child]<this.elem[child +1]){
                child++;}if(this.elem[child]>this.elem[parent]){swap(this.elem, child, parent);
                parent = child;
                child =2* parent +1;}else{break;}}}}

升序堆排序:

/**
     * 堆排序
     * @param arr 排序对象
     * @return 返回排序好的对象
     */publicint[]heapSort(int[] arr){creatBigHeap(arr);int end = usedSize -1;for(int i = end; i >0; i--){swap(this.elem,0, i);shiftDown(0,i);}returnthis.elem;}

3.TopK问题

topK问题指的是在一个很大数量级的数据中找出最大或者最小的前k个元素,比如在100万个数据中找到最大的10个数。

思路1: 先对数组排序再取前k个最值元素,不推荐,因为太慢了,只需要前k最值元素,没有必要对整个数组排序,况且数组元素个数是非常大的。

思路2: 使用堆,如求前k个最大的元素,可以创建一个基于大根堆的优先队列,将所有数据入队,再出队k个,这k个元素就是前k个最大的元素。

思路3: topK问题标准解决思路,topK问题的根本就是从一个大数量级的数组中找到最大或者最小的k个数,以求前k个最大元素为例,首先可以将数组前k个元素建成一个大小为k的小根堆,为什么是建造小根堆呢?因为堆顶元素是最小的,那么这个大小为k的小根堆堆顶元素top是这k个数字中最小的,然后遍历剩下的数组元素,如果比top大,就说明该元素可能是前k大的元素,此时的top一定不是前k个最大元素中的一员,使用该元素替换堆中的堆顶元素top,并重新调整为小根堆,遍历完数组后,这个大小为k的小根堆中的元素就是前k个最大的元素,简单说就是使用一个大小为k的堆来储存最大或最小的前k个元素。同理找前k个最小的元素需要使用大根堆,思路与求前k个最大元素是一样的。

我们来实现一下topK的代码,这里我们就不自己建堆了,我们使用java中的优先队列来实现,无参数构造的优先队列就是一个小根堆(默认)。

importjava.util.Comparator;importjava.util.PriorityQueue;publicclassTopK{/**
     * 求数组中最大k个元素
     * @param arr 数据
     * @param k 最大元素个数
     * @return 小根堆
     */publicstaticPriorityQueue<Integer>topKMax(int[] arr,int k){PriorityQueue<Integer> priorityQueue =newPriorityQueue<>();if(k <=0)return priorityQueue;for(int i =0; i < arr.length; i++){if(i < k){
                priorityQueue.offer(arr[i]);}else{if(priorityQueue.isEmpty())return priorityQueue;int top = priorityQueue.peek();if(arr[i]> top){//1.堆顶出队
                    priorityQueue.poll();//2.入队并重新调整为小根堆
                    priorityQueue.offer(arr[i]);}}}return priorityQueue;}/**
     * 求前k个最小的元素
     * @param arr 数据
     * @param k 最小的元素个数
     * @return 大根堆
     */publicstaticPriorityQueue<Integer>topKMin(int[] arr,int k){//建大堆PriorityQueue<Integer> priorityQueue =newPriorityQueue<>(newComparator<Integer>(){@Overridepublicintcompare(Integer o1,Integer o2){return o2 - o1;}});if(k <=0)return priorityQueue;for(int i =0; i < arr.length; i++){if(i < k){
                priorityQueue.offer(arr[i]);}else{if(priorityQueue.isEmpty())return priorityQueue;int top = priorityQueue.peek();if(arr[i]< top){//1.堆顶出队
                    priorityQueue.poll();//2.入队并重新调整为大根堆
                    priorityQueue.offer(arr[i]);}}}return priorityQueue;}publicstaticvoidmain(String[] args){int[] data ={3,2,4,5,6,1,7,9,8};PriorityQueue<Integer> ret =topKMax(data,3);//7,8,9System.out.print("前k个最大的元素:");System.out.println(ret);
        ret =topKMin(data,3);System.out.print("前k个最小的元素:");System.out.println(ret);}}

数组样例为int[] data = {3,2,4,5,6,1,7,9,8};k=3。
3-1
知道了topK问题解决问题,我们趁热打铁来看下面这一道题:
373. 查找和最小的 K 对数字
给定两个以 升序排列 的整数数组

nums1

nums2

, 以及一个整数

k


定义一对值

(u,v)

,其中第一个元素来自

nums1

,第二个元素来自

nums2


请找到和最小的

k

个数对

(u1,v1)

,

(u2,v2)

(uk,vk)

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数:
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数:
     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

示例 3:

输入: nums1 = [1,2], nums2 = [3], k = 3 
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]

提示:

  • 1 <= nums1.length, nums2.length <= 105
  • -109 <= nums1[i], nums2[i] <= 109
  • nums1nums2 均为升序排列
  • 1 <= k <= 1000

💡解决思路:
其实这道题的思路与topK问题中求前k个最小元素的思路是一样的,只不过这里的元素是一个数对。
第一步,建造一个大根堆,大小为

k

,用来存放前

k

个和最小的数对。
第二步,注意到给定的两个目标数组都是升序排列的,如果

k

小于数组的长度,那么数对中的一个数一定在数组前k个元素中,遍历两数组

min(k,len)

的元素(其中

len

为数组长度),构造数对,将前

k

个数对放进大根堆,并调整。
第三步,遍历完按照第二步所构造的数对,如果数对和比堆顶数对和小,则替换堆顶的元素,最终大根堆中的数对就是最小的

k

组数字对。

publicList<List<Integer>>kSmallestPairs(int[] nums1,int[] nums2,int k){//构造大根堆PriorityQueue<List<Integer>> priorityQueue =newPriorityQueue(newComparator<List<Integer>>(){@Overridepublicintcompare(List<Integer> o1,List<Integer> o2){return o2.get(0)+ o2.get(1)- o1.get(0)- o1.get(1);}});for(int i =0; i <Math.min(k,nums1.length); i++){for(int j =0; j <Math.min(k, nums2.length); j++){List<Integer> digits =newArrayList<>();
                digits.add(nums1[i]);
                digits.add(nums2[j]);if(priorityQueue.size()< k){
                    priorityQueue.offer(digits);}else{int topAdd = priorityQueue.peek().get(0)+ priorityQueue.peek().get(1);if(digits.get(0)+ digits.get(1)< topAdd){//1.出堆顶元素
                        priorityQueue.poll();//2.入目标元素
                        priorityQueue.offer(digits);}else{//3.因为两个数组升序排列,此时如果比堆顶元素大,则后面的组合必然比堆顶元素大,此时应该直接结束循环break;}}}}//返回值是List所以先得将优先队列转换成List再返回List<List<Integer>> ret =newArrayList(priorityQueue);return ret;}

其他练习题:
215. 数组中的第K个最大元素

堆与优先队列就介绍到这里了,下期再见!


觉得文章写得不错的老铁们,点赞评论关注走一波!谢谢啦!
1-99


本文转载自: https://blog.csdn.net/m0_59139260/article/details/122843013
版权归原作者 未见花闻 所有, 如有侵权,请联系我们删除。

“【JavaSE|数据结构】堆,优先级队列,topK问题与堆排序”的评论:

还没有评论