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

Top K算法(问题) 小顶堆指定排序实现及源码解析

程序员文章站 2024-03-22 23:22:46
...

本文基于大家了解了有限队列进行的,如果不了解请点击下方传送门,进入了解,大佬文章里面也对这个队列如何使用有很详细的解答。
传送门:PriorityQueue(优先队列参考)https://blog.csdn.net/u010623927/article/details/87179364

package com.example.tran;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
/**
 * @author chengtonghua
 * @date 2021-02-09
 */
public class Quene {

    public static void main(String[] args) {

        //优先队列,可以指定其排序升序或者降序
        Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7,sortType);
        Random rand = new Random();
        for (int i = 0; i < 100; i++) {
            integerPriorityQueue.add(Integer.valueOf(rand.nextInt(1000)));
        }
        for (int i = 0; i < 7; i++) {
            Integer in = integerPriorityQueue.poll();
            System.out.println("Processing Integer:" + in);
        }
    }

    //匿名Comparator实现
    public static Comparator<Integer> sortType = new Comparator<Integer>() {
        public int compare(Integer c1, Integer c2) {
            return (int) (c2 - c1);
        }
    };
}

看上面的代码,自定义了排序规则但是在插入的时候只是执行了add方法,这个时候我们并没有看到我们指定的排序规则生效对不对。
这个时候先别急,PriorityQueue插入的时候会执行判断,当前对象是否有指定过排序规则,如果有则执行排序规则,没有的话则执行;
不信的话请看源码

  /**
     * Inserts the specified element into this priority queue.
     *
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws ClassCastException if the specified element cannot be
     *         compared with elements currently in this priority queue
     *         according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
    public boolean add(E e) {
        return offer(e);
    }

    /**
     * Inserts the specified element into this priority queue.
     *
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws ClassCastException if the specified element cannot be
     *         compared with elements currently in this priority queue
     *         according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
public boolean offer(E e) {
        if (e == null)//不允许放入null元素
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);//自动扩容
        siftUp(i, e);//执行插入逻辑
        size = i + 1;
        return true;
    }

如果不指定排序方式则按照默认排序方式进行插入的逻辑(默认排序根据代码可以看出是从小到大进行的排序)

  private static <T> void siftUpComparable(int k, T x, Object[] es) {
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = es[parent];
            if (key.compareTo((T) e) >= 0)
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = key;
    }

指定排序方式之后的插入逻辑(最上面我指定是从大到小)

  private static <T> void siftUpUsingComparator(
    int k, T x, Object[] es, Comparator<? super T> cmp) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (cmp.compare(x, (T) e) >= 0)//执行自定义的比器方法
            break;
        es[k] = e;
        k = parent;
    }
      es[k] = x;
  }

看到了上面的插入逻辑应该明白了,优先队列插入时就已经按照我们指定的排序规则进行了排序,这样不论是获取最大的K个数字或者获取最小的K个数字都可以使用优先队列进行执行。

相关标签: java后台 队列