精华内容
下载资源
问答
  • 优先队列实现原理分析

    千次阅读 2017-07-03 14:16:02
    不管是在操作系统的进程调度中,还是在相关的图算法比如Prim算法和Dijkstra算法中,我们都可以看到优先队列的身影,本文我们就来分析一下优先队列实现原理优先队列以操作系统的进程调度为例,比如我们在使用手机...

    来源:ziwenxie,
    www.ziwenxie.site/2017/03/30/algorithm-priority-queue/

    原文

    优先队列是在实际工程中被广泛应用的一种数据结构,不管是在操作系统的进程调度中,还是在相关的图算法比如Prim算法和Dijkstra算法中,我们都可以看到优先队列的身影,本文我们就来分析一下优先队列的实现原理。

    优先队列

    以操作系统的进程调度为例,比如我们在使用手机的过程中,手机分配给来电的优先级都会比其它程序高,在这个业务场景中,我们不要求所有元素全部有序,因为我们需要处理的只是当前键值最大的元素(优先级最高的进程)。在这种情况下,我们需要实现的只是删除最大的元素(获取优先级最高的进程)和插入新的元素(插入新的进程),这种数据结构就叫做优先队列。

    我们先来定义一个优先队列,下面我们将使用pq[]来保存相关的元素,在构造函数中可以指定堆的初始化大小,如果不指定初始化大小值,默认初始化值为1。p.s: 在下面我们会实现相关的resize()方法用来动态调整数组的大小。

    public class MaxPQ<Key> implements Iterable<Key> {
        private Key[] pq;                    // store items at indices 1 to n
        private int n;                       // number of items on priority queue
        private Comparator<Key> comparator;  // optional Comparator
        /**
         * Initializes an empty priority queue with the given initial capacity.
         *
         * @param  initCapacity the initial capacity of this priority queue
         */
        public MaxPQ(int initCapacity) {
            pq = (Key[]) new Object[initCapacity + 1];
            n = 0;
        }
        /**
         * Initializes an empty priority queue.
         */
        public MaxPQ() {
            this(1);
        }
    }

    堆的基本概念

    在正式进入优先队列分析之前,我们有必要先了解一下对于堆的相关操作。我们定义当一棵二叉树的每个结点都要大于等于它的两个子结点的时候,称这棵二叉树堆有序。如下图就是一棵典型的堆有序的完全二叉树。

    heap

    堆上浮和下沉操作

    对了保证堆有序,对于堆我们要对它进行上浮和下沉操作,我们先来实现两个常用的工具方法,其中less()用于比较两个元素的大小,exch()用于交换数组的两个元素:

    private boolean less(int i, int j) {
        if (comparator == null) {
            return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
        }
        else {
            return comparator.compare(pq[i], pq[j]) < 0;
        }
    }
    private void exch(int i, int j) {
        Key swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
    }

    上浮操作

    根据下图我们首先来分析一下上浮操作,以swim(5)为例子,我们来看一下上浮的过程。对于堆我们进行上浮的目的是保持堆有序性,即一个结点的值大于它的子结点的值,所以我们将a[5]和它的父结点a[2]相比较,如果它大于父结点的值,我们就交换两者,然后继续swim(2)。
    这里写图片描述

    具体的实现代码如下:

    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }

    下沉操作

    根据下图我们来分析一下下沉操作,以sink(2)为例子,我们先将结点a[2]和它两个子结点中较小的结点相比较,如果小于子结点,我们就交换两者,然后继续sink(5)。
    这里写图片描述

    具体的实现代码如下:

    private void sink(int k) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    实现

    我们来分析一下插入一个元素的过程,如果我们要在堆中新插入一个元素S的话,首先我们默认将这个元素插入到数组中pq[++n] 中(数组是从1开始计数的)。当我们插入S后,打破了堆的有序性,所以我们采用上浮操作来维持堆的有序性,当上浮操作结束之后,我们依然可以保证根结点的元素是数组中最大的元素。

    接下来我们来看一下删除最大元素的过程,我们首先将最大的元素a[1]和a[n]交换,然后我们删除最大元素a[n],这个时候堆的有序性已经被打破了,所以我们继续通过下沉操作来重新维持堆的有序性,保持根结点元素是所有元素中最大的元素。
    这里写图片描述

    插入的实现代码如下:

    /**
     * Adds a new key to this priority queue.
     *
     * @param  x the new key to add to this priority queue
     */
    public void insert(Key x) {
        // double size of array if necessary
        if (n >= pq.length - 1) resize(2 * pq.length);
        // add x, and percolate it up to maintain heap invariant
        pq[++n] = x;
        swim(n);
        assert isMaxHeap();
    }
    

    删除的实现代码如下:

    /**
     * Removes a maximum key and returns its associated index.
     *
     * @return an index associated with a maximum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key delMax() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        Key max = pq[1];
        exch(1, n);
        n--;
        sink(1);
        pq[n+1] = null;     // to avoid loiterig and help with garbage collection
        if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);
        assert isMaxHeap();
        return max;
    }

    上面我们在insert()过程中用到了resize()函数,它用于动态数组的大小,具体的实现代码如下:

    // helper function to double the size of the heap array
    private void resize(int capacity) {
        assert capacity > n;
        Key[] temp = (Key[]) new Object[capacity];
        for (int i = 1; i <= n; i++) {
            temp[i] = pq[i];
        }
        pq = temp;
    }
    public boolean isEmpty() {
        return n == 0;
    }

    而isMaxHeap()则用于判断当前数组是否满足堆有序原则,这在debug的时候非常的有用,具体的实现代码如下:

    // is pq[1..N] a max heap?
    private boolean isMaxHeap() {
        return isMaxHeap(1);
    }
    // is subtree of pq[1..n] rooted at k a max heap?
    private boolean isMaxHeap(int k) {
        if (k > n) return true;
        int left = 2*k;
        int right = 2*k + 1;
        if (left  <= n && less(k, left))  return false;
        if (right <= n && less(k, right)) return false;
        return isMaxHeap(left) && isMaxHeap(right);
    }
    

    到此我们的优先队列已经差不多完成了,注意我们上面实现了Iterable接口,所以我们来实现iterator()方法:

    /**
     * Returns an iterator that iterates over the keys on this priority queue
     * in descending order.
     * The iterator doesn't implement remove() since it's optional.
     *
     * @return an iterator that iterates over the keys in descending order
     */
    public Iterator<Key> iterator() {
        return new HeapIterator();
    }
    private class HeapIterator implements Iterator<Key> {
        // create a new pq
        private MaxPQ<Key> copy;
        // add all items to copy of heap
        // takes linear time since already in heap order so no keys move
        public HeapIterator() {
            if (comparator == null) copy = new MaxPQ<Key>(size());
            else                    copy = new MaxPQ<Key>(size(), comparator);
            for (int i = 1; i <= n; i++)
                copy.insert(pq[i]);
        }
        public boolean hasNext()  { return !copy.isEmpty();                     }
        public void remove()      { throw new UnsupportedOperationException();  }
        public Key next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.delMax();
        }
    }

    堆排序

    将上面的优先队列稍微做一下改进,我们便可以实现堆排序,即对pq[]中的元素进行排序。对于堆排序的具体实现,下面我们分为两个步骤:

    首先我们先来构造一个堆。
    然后通过下沉的方式进行排序。

    堆排序的实现代码非常的简短,我们首先来看一下具体的代码实现,然后我们再具体分析它的实现原理:

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param pq the array to be sorted
     */
    public static void sort(Comparable[] pq) {
        int n = pq.length;
        for (int k = n/2; k >= 1; k--)
            sink(pq, k, n);
        while (n > 1) {
            exch(pq, 1, n--);
            sink(pq, 1, n);
        }
    }

    首先我们来看一下堆的构造过程(下图中的左图)。我们采用的方法是从右至左用sink()方法构造子堆。我们只需要扫描数组中的一半元素,即5, 4, 3, 2, 1。这样通过这几个步骤,我们可以得到一个堆有序的数组,即每个结点的大小都大于它的两个结点,并使最大元素位于数组的开头。

    接下来我们来分析一下下沉排序的实现(下图中的右图),这里我们采取的方法是每次都将最大的元素删除,然后重新通过sink()来维持堆有序,这样每一次sink()操作我们都可以的到数组中最大的元素。
    这里写图片描述

    Referencs

    ALGORITHM-4TH
    http://algs4.cs.princeton.edu/home/

    展开全文
  • 一、什么是优先队列优先队列不是按照普通对象先进先出原FIFO则进行数据操作,其中的元素有优先级属性,优先级高的元素先出队。本文提到的PriorityQueue队列,是基于最小堆原理实现。需要注意:PriorityQueue继承了...

    转载: http://blog.csdn.net/lisuyibmd/article/details/53205403
    一、什么是优先队列

    优先队列不是按照普通对象先进先出原FIFO则进行数据操作,其中的元素有优先级属性,优先级高的元素先出队。本文提到的PriorityQueue队列,是基于最小堆原理实现。

    需要注意:PriorityQueue继承了AbstractQueue没有实现BlockingQueue接口,所以没有take阻塞方法。

    二、什么是最小堆

    最小堆是一个完全二叉树,所谓的完全二叉树是一种没有空节点的二叉树。
    
    最小堆的完全二叉树有一个特性是根节点必定是最小节点,子女节点一定大于其父节点。还有一个特性是叶子节点数量=全部非叶子节点数量+1
    
    在 PriorityQueue队列中,基于数组保存了完全二叉树。所以在已知任意一个节点在数组中的位置,就可以通过一个公式推算出其左子树和右子树的下标。已知节点下标是i,那么他的左子树是2*i+1,右子树是2*i+2。
    

    三、PriorityQueue队列的存取原理

     1、首先看下源码
    

    [java] view plain copy 在CODE上查看代码片派生到我的代码片

    /** 
     * Inserts item x at position k, maintaining heap invariant by 
     * promoting x up the tree until it is greater than or equal to 
     * its parent, or is the root. 
     * 
     * To simplify and speed up coercions and comparisons. the 
     * Comparable and Comparator versions are separated into different 
     * methods that are otherwise identical. (Similarly for siftDown.) 
     * 
     * @param k the position to fill 
     * @param x the item to insert 
     */  
    private void siftUp(int k, E x) {  
        if (comparator != null)  
            siftUpUsingComparator(k, x);  
        else  
            siftUpComparable(k, x);  
    }  

    在调用offer(E e)方法入队时,首先进行非null判断,然后是grow方法扩容,紧接着就是siftUp方法调整节点位置,那么是如何调整的呢?为什么要调整?
    2、为什么要调整节点顺序?

    因为这是一个最小堆,最小堆必须要严格按照子节点大于父亲节点的顺序做数组中存放。

    3、如何调整?

    siftup方法有个if-else判断,如果有比较器,则使用siftUpUsingComparator(k, x);如果没有则调用siftUpComparable(k, x);这个方法会默认给一个比较器。

    比较什么呢??我们说最小堆实现了这个队列,队列一定有入队操作,入队是元素首先进入队列尾,然后和自己的父节点比较,像冒泡一样将该节点冒到合适的位置,即比自己的父亲节点大,比自己的儿子节点小。

    [java] view plain copy 在CODE上查看代码片派生到我的代码片
    private void siftUpComparable(int k, E x) {  
           Comparable<? super E> key = (Comparable<? super E>) x;  
           while (k > 0) {  
               int parent = (k - 1) >>> 1;  
               Object e = queue[parent];  
               if (key.compareTo((E) e) >= 0)  
                   break;  
               queue[k] = e;  
               k = parent;  
           }  
           queue[k] = key;  
       }  
    4、如何出队
    [java] view plain copy 在CODE上查看代码片派生到我的代码片
    public E poll() {  
            if (size == 0)  
                return null;  
            int s = --size;  
            modCount++;  
            E result = (E) queue[0];  
            E x = (E) queue[s];  
            queue[s] = null;  
            if (s != 0)  
                siftDown(0, x);  
            return result;  
        }  
    
     private void siftDownComparable(int k, E x) {  
            Comparable<? super E> key = (Comparable<? super E>)x;  
            int half = size >>> 1;        // loop while a non-leaf  
            while (k < half) {  
                int child = (k << 1) + 1; // assume left child is least  
                Object c = queue[child];  
                int right = child + 1;  
                if (right < size &&  
                    ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)  
                    c = queue[child = right];  
                if (key.compareTo((E) c) <= 0)  
                    break;  
                queue[k] = c;  
                k = child;  
            }  
            queue[k] = key;  
        }  

    出队和入队原理正好相反,每次出队也要进行siftDown操作,对元素顺序重新整理。

    四、总结

    PriorityQueue队列不适合进场出队入队的频繁操作,但是他的优先级特性非常适合一些对顺序有要求的数据处理场合。

    版权声明:沉淀、积累,我追求工匠精神

    展开全文
  • java学习笔记之优先队列实现原理

    千次阅读 2019-05-05 12:56:12
    目录一、二叉堆的基本原理(一) 什么是二叉堆?(二) 堆的用途(三) 堆的...优先队列一般基于二叉堆实现。 本文会分析java中几种常见的优先队列:PriorityQueue、PriorityBlockingQueue、DelayQueue、DelayedWorkQue...

    普通的队列是先进先出的数据结构,而优先队列为元素赋予优先级,具有最高优先级的元素成为队列首部。

    优先队列一般基于二叉堆实现。

    本文会分析java中几种常见的优先队列:PriorityQueuePriorityBlockingQueueDelayQueueDelayedWorkQueue

    一、二叉堆的基本原理

    (一) 什么是二叉堆?

    • 完全二叉树
    • 堆的根节点的优先级最大(即最大或最小)
    • 父节点的优先级必定大于子节点,兄弟节点的优先级不确定谁大谁小
    时间复杂度
    插入 O(log n)
    删除 O(log n)
    构造 O(n)

    (二) 堆的用途

    • 取最值

    (三) 堆的基本操作

    1. 插入

    往堆插入元素,基本思想是从最后一个位置开始,通过上浮操作不断调整位置,直到满足父节点的优先级必定大于子节点这个条件

    上浮

    上浮是往二叉堆添加元素用到的操作,它其实是不断的调整k的位置为父元素的位置直到满足条件为止。

    // 用数组表示堆
    Object []objs = new Object[10];
    /**
     * 上浮:
     * k表示堆的最后一个位置;
     * obj表示将要插入的元素。
     */
    private void siftUp(int k, Object obj) {
        // 1. 判断k是否为根元素的位置0,如果是则直接赋值
        while(k>0) {
             // 2. 获取父元素的位置,parent = (k-1)/2
             int parent = (k-1) >>> 1;
             // 3. 如果父元素的优先级大于等于obj,跳出循环并插入obj
             if(objs[parent] >= obj) {
                 break;
    		 }
    		 // 4. 如果父元素的优先级小于obj,将父元素赋值到k的位置,更改k为父元素的位置,继续循环
    		 objs[k] = objs[parent];
    		 k = parent;
        }
        // 5. 为obj赋值
        objs[k] = obj;
    }
    /**
     * 添加元素,不考虑数组扩容的情况。
     * 假设size表示当前堆包含的元素个数(注意不一定等于上面定义的10)
     */
    public void add(Object obj) {
        if(size==0) {
            objs[0] = obj;
        } else {
            siftUp(size, obj);
            size++;
    	}
    }
    

    2. 删除

    删除指定位置的元素,其基本思想是从指定位置开始,把最后一个元素放到被删除元素的位置,通过下沉或者上浮操作,使得堆满足父元素优先级大于子元素的条件。

    下沉

    下沉是删除时用到的操作。它是把最后一个元素放到被删除元素的位置,然后重新调整使得堆满足条件的过程。

    • 被删除元素的位置位于最后一个元素的父元素的位置后面时,可以直接把最后一个元素插入到被删除元素的位置;然后再进行上浮操作。
    • 否则,需要执行下沉操作。
    // 用数组表示堆
    Object []objs = new Object[10];
    /**
     * k被删除元素的位置;
     * obj堆的最后一个元素;
     *  假设size为当前堆包含元素的个数(不一定是上面定义的10)
     */
    private void siftDown(int k, Object obj) {
        // 1. 找到最后一个元素的父节点的位置, (最后一个元素位置-1) / 2
        int parent = (size-1-1) >>> 1;
        // 2. 判断k是否在父节点位置之后,如果在之前则需要下沉操作
        while(k <= parent) {
        	// 3.获取k的左右子节点的位置
        	int left = k<<<2 +1;
        	int right = left+1;
        	// 4.选择左右子节点中优先级最高的一个
        	int best;
        	if (objs[left] > objs[right]) {
    			best = left;
    		} else {
    			best = right;
    		}
    		// 5.判断obj和best的优先级谁高。如果obj优先级高,则跳出循环直接赋值,否则继续下沉
    		if (obj >= objs[best]) {
    			break;
    		}
    		objs[k] = objs[best];
    		k = best;
        }
        // 6.赋值
        objs[k] = obj;
    }
    
    /**
     * 删除第p个元素。
     */
    public void remove(int p) {
        // 1.获取最后一个元素
        Object obj = objs[size-1];
        // 2.如果p不等于最后一个元素
        if (p != size-1) {
    		// 3.把最后一个元素和p进行下沉操作
        	siftDown(p, obj);
        	if(objs[p] == obj) {
    			// 4. 上浮
    			siftUp(p, obj);
    		}
    	}
    	size--;
    }
    

    二、PriorityQueue

    (一) PriorityQueue是什么?

    • PriorityQueue是基于二叉堆原理的优先队列,队列用动态数组实现。
    • 它是非阻塞的、非线程安全的;

    PriorityQueue内部维护了几个重要属性:

    类型 含义
    queue Object[] 代表PriorityQueue的队列,存放元素
    size int 当前队列包含元素个数
    comparator Comparator PriorityQueue根据比较器对元素优先级排序
    modCount int 记录队列被修改的次数

    (二) PriorityQueue的使用

    PriorityQueue的使用非常简单,一笔带过。

    public static void main(String[] args) {
       PriorityQueue<String> queue = new PriorityQueue<>();
       queue.add("hello");
       System.out.println(queue.peek());
       queue.remove("hello");
       System.out.println(queue.peek());
    }
    

    (三) PriorityQueue的实现原理

    PriorityQueue的基本原理和第一部分讲的基本一致。

    插入

    1. 如果当前元素个数达到数组长度,则扩容;
      1.1 如果数组长度小于64,直接扩容1倍
      1.2 否则扩容0.5倍
    2. 增加元素个数
    3. 上浮操作,找到合适的位置插入。在上浮的时候,如果comparator存在则用它确定优先级,否则用自然顺序确定优先级。
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            // 扩容
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            // 上浮
            siftUp(i, e);
        return true;
    }
    

    删除

    1. 获取最后一个元素
    2. 将待删除的位置i和最后一个元素做下沉操作
    3. 如果没有执行下沉操作,那么表示待删除的位置i是叶节点,需要通过上浮调整二叉堆
    4. 执行上浮操作
    private E removeAt(int i) {
        modCount++;
        int s = --size;
        if (s == i) // removed last element
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            siftDown(i, moved);
            if (queue[i] == moved) {
                siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }
    

    三、PriorityBlockingQueue

    (一) PriorityBlockingQueue是什么?

    • PriorityQueue线程安全版本
    • 同样是基于二叉堆的原理,用动态数组实现
    • 阻塞的、线程安全的

    (二) PriorityBlockingQueue的实现原理

    插入

    原理基本和PriorityQueue一样

    1. 加锁
    2. 是否需要扩容,扩容原理和PriorityQueue一样
    3. 上浮
    4. 解锁
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        int n, cap;
        Object[] array;
        while ((n = size) >= (cap = (array = queue).length))
            tryGrow(array, cap);
        try {
            Comparator<? super E> cmp = comparator;
            if (cmp == null)
                siftUpComparable(n, e, array);
            else
                siftUpUsingComparator(n, e, array, cmp);
            size = n + 1;
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
        return true;
    }
    

    删除

    基本原理和PriorityQueue一致,只是使用ReentrantLock保证线程安全。

    四、DelayQueue

    • 基于PriorityQueue实现的延迟队列
    • 它的删除、插入操作和PriorityQueue基本一致,主要的区别在与poll()take()等方法。PriorityQueue是只要队列首部有数据就除移,而DelayQueue还需要判断是否达到除移的时间。
    • 至于take()poll()方法的区别在于,take()会阻塞,而poll()直接返回。

    五、DelayedWorkQueue

    原理与DelayQueue相同,不知道JDK开发团队为何重复造一个轮子。

    六、一图胜千言

    添加

    在这里插入图片描述

    在这里插入图片描述

    删除

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    七、F&Q

    1、侄节点与叔节点的大小关系?
    没有规定两种的大小关系,叔节点的优先级可以比侄节点大也可以小。

    展开全文
  • 这篇文章主要介绍了Java的优先队列PriorityQueue原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下一、优先队列概述优先队列PriorityQueue是Queue接口的...

    这篇文章主要介绍了Java的优先队列PriorityQueue原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

    一、优先队列概述

    优先队列PriorityQueue是Queue接口的实现,可以对其中元素进行排序,

    可以放基本数据类型的包装类(如:Integer,Long等)或自定义的类

    对于基本数据类型的包装器类,优先队列中元素默认排列顺序是升序排列

    但对于自己定义的类来说,需要自己定义比较器

    二、常用方法

    peek()//返回队首元素

    poll()//返回队首元素,队首元素出队列

    add()//添加元素

    size()//返回队列元素个数

    isEmpty()//判断队列是否为空,为空返回true,不空返回false

    三、优先队列的使用

    1.队列保存的是基本数据类型的包装类

    //自定义比较器,降序排列

    static Comparator cmp = new Comparator() {

    public int compare(Integer e1, Integer e2) {

    return e2 - e1;

    }

    };

    public static void main(String[] args) {

    //不用比较器,默认升序排列

    Queue q = new PriorityQueue<>();

    q.add(3);

    q.add(2);

    q.add(4);

    while(!q.isEmpty())

    {

    System.out.print(q.poll()+" ");

    }

    /**

    * 输出结果

    * 2 3 4

    */

    //使用自定义比较器,降序排列

    Queue qq = new PriorityQueue<>(cmp);

    qq.add(3);

    qq.add(2);

    qq.add(4);

    while(!qq.isEmpty())

    {

    System.out.print(qq.poll()+" ");

    }

    /**

    * 输出结果

    * 4 3 2

    */

    }

    2.队列保存的是自定义类

    //矩形类

    class Node{

    public Node(int chang,int kuan)

    {

    this.chang=chang;

    this.kuan=kuan;

    }

    int chang;

    int kuan;

    }

    public class Test {

    //自定义比较类,先比较长,长升序排列,若长相等再比较宽,宽降序

    static Comparator cNode=new Comparator() {

    public int compare(Node o1, Node o2) {

    if(o1.chang!=o2.chang)

    return o1.chang-o2.chang;

    else

    return o2.kuan-o1.kuan;

    }

    };

    public static void main(String[] args) {

    Queue q=new PriorityQueue<>(cNode);

    Node n1=new Node(1, 2);

    Node n2=new Node(2, 5);

    Node n3=new Node(2, 3);

    Node n4=new Node(1, 2);

    q.add(n1);

    q.add(n2);

    q.add(n3);

    Node n;

    while(!q.isEmpty())

    {

    n=q.poll();

    System.out.println("长: "+n.chang+" 宽:" +n.kuan);

    }

    /**

    * 输出结果

    * 长: 1 宽:2

    * 长: 2 宽:5

    * 长: 2 宽:3

    */

    }

    }

    3.优先队列遍历

    PriorityQueue的iterator()不保证以任何特定顺序遍历队列元素。

    若想按特定顺序遍历,先将队列转成数组,然后排序遍历

    示例

    Queue q = new PriorityQueue<>(cmp);

    int[] nums= {2,5,3,4,1,6};

    for(int i:nums)

    {

    q.add(i);

    }

    Object[] nn=q.toArray();

    Arrays.sort(nn);

    for(int i=nn.length-1;i>=0;i--)

    System.out.print((int)nn[i]+" ");

    /**

    * 输出结果

    * 6 5 4 3 2 1

    */

    4.比较器生降序说明

    Comparator cmp = new Comparator() {

    public int compare(Object o1, Object o2) {

    //升序

    return o1-o2;

    //降序

    return o2-o1;

    }

    };

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

    展开全文
  • 优先队列原理实现

    2019-09-26 14:01:42
    优先队列是一种用来维护一组元素构成...优先队列包括最大优先队列和最小优先队列优先队列的应用比较广泛,比如作业系统中的调度程序,当一个作业完成后,需要在所有等待调度的作业中选择一个优先级最高的作业来执...
  • 优先队列与索引优先队列优先队列原理大家应该比较熟悉,本质上就是利用完全二叉树的结构实现以log2n的时间复杂度删除队列中的最小对象(这里以小堆顶为例)。完全二叉树又可以通过数组下标实现索引,当插入一个对象...
  • 一、优先队列 优先队列是一种用来维护由一组元素构成的集合S的数据结构,其中的每一个元素都有一个相关的值,称为关键字。一个最大优先队列支持以下操作: Insert(S, x):把元素x插入集合S中。 Maximum(S):返回S中...
  • 转自:优先队列原理实现  优先队列是一种用来维护一组元素构成的结合S的数据结构,其中每个元素都有一个关键字key,元素之间的比较都是通过key来比较的。优先队列包括最大优先队列和最小优先队列优先队列的...
  • 原理: 传统的队列是先进先出的数据结构,队列的重要变种称为优先级队列 二叉堆常见的遍体:最小堆(其中最小的键在前面)和最大堆(其中最大的键值总是在前面)   代码实现        ...
  • 优先队列 优先级队列为,首部元素最大,总是删除当前最大元素。...堆排序,通过插入一列元素然后一个个地删掉其中最小的元素,我们可以用优先队列实现排序算法。 初级实现 4种基础数据结构:有序或无序的数组
  • 优先队列一般基于二叉堆实现。本文会分析java中几种常见的优先队列:PriorityQueue、PriorityBlockingQueue、DelayQueue、DelayedWorkQueue。 二叉堆的基本原理 (一)什么是二叉堆 完全二叉树 堆的根节点的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 384
精华内容 153
关键字:

优先队列实现原理