PriorityQueue优先队列中比较器Comparator的使用 |
您所在的位置：网站首页 › compare的比较级是什么 › PriorityQueue优先队列中比较器Comparator的使用 |
PriorityQueue优先队列中比较器Comparator的使用
|
优先队列
java中的优先队列使用堆实现的，所以优先队列我们通常是拿来当大顶堆小顶堆使用 大顶堆和小顶堆的作用就是当我们想要获取大量数据的前几个最大或者最小的数据时使用的，因为如果对所有数据排序然后取前几个，时间复杂度最小也是O(nlogn)，使用堆的话时间复杂度为O(nlongm)，而 m 就是我们想要进行获取的前几个数，一般为常量，比如想要获取学校n个同学里面前8名，使用大顶堆获取的时间复杂度就是O(nlog8)=O(n)。 如图所示是一种自下向上的建堆过程： 在java中优先队列的创建方法： //创建优先队列对象，默认建立小顶堆 PriorityQueue heap = new PriorityQueue(); //将一个元素放入优先队列(堆)中 heap.offer(5); //获取优先队列第一个元素(堆顶元素),但是不出队 int n = heap.peek(); //获取优先队列第一个元素(堆顶元素),出队 int n = heap.poll(); 入队接下来我们看一下入队的源码： public boolean offer(E e) { //如果入队的元素为空，则抛出异常 if (e == null) throw new NullPointerException(); //modCount用来记录该队列修改的次数 modCount++; //获取队列的大小，由于该队列是顺序存储也就是使用数组存储的二叉树，所以元素个数可以视作最后一个元素的下一个位置 //也就是要插入的位置 int i = size; //判断队列是否需要扩容 if (i >= queue.length) grow(i + 1); //自下而上的调整堆的主方法 siftUp(i, e); size = i + 1; return true; }上面的如对方法中使用siftUp()方法来进行调整堆： //k为插入位置，x为插入元素 private void siftUp(int k, E x) { // 如果传入了比较器，就使用传入的比较器进行比较来调整堆 if (comparator != null) siftUpUsingComparator(k, x, queue, comparator); else // 如果没有传入比较器，就使用原始比较器进行比较来调整堆 siftUpComparable(k, x, queue); }看一下这两个方法： private static void siftUpComparable(int k, T x, Object[] es) { Comparable key = (Comparable) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = es[parent]; //这就是原始比较器，如果返回的值大于等于0则结束不进行交换结点 if (key.compareTo((T) e) >= 0) break; //否则交换位置继续往上比较 es[k] = e; k = parent; } es[k] = key; } private static void siftUpUsingComparator( int k, T x, Object[] es, Comparator cmp) { while (k > 0) { int parent = (k - 1) >>> 1; Object e = es[parent]; //使用自己的构造器也一样，当返回结果小于0时才进行交换 if (cmp.compare(x, (T) e) >= 0) break; es[k] = e; k = parent; } es[k] = x; } 出队和如对相反，出队时要拿走对顶元素，所以采用自顶而下的调整方式，也就是比较删除结点的左右孩子来判断谁交换上去 |
【本文地址】
今日新闻 |
推荐新闻 |