這篇文章主要為大家詳細介紹了JDK源碼之PriorityQueue,具有一定的參考價值,有興趣的小伙伴們可以參考一下
##一.優先隊列的應用
優先隊列在程式開發中屢見不鮮,例如作業系統在進行進程調度時一種可行的演算法是使用優先隊列,當一個新的進程被fork()出來後,首先將它放到隊列的最後,而作業系統內部的Scheduler負責不斷地從這個優先隊列中取出優先權較高的進程執行;爬蟲系統在執行時往往也需要從一個優先權隊列中二.優先佇列的實作原理
優先佇列的實作方式是使用二元堆的結構,需要滿足以下兩個性質(Heap property),這裡以小頂堆為例講解: 1.任何結點的值都小於或等於其子節點的值。 2.所有結點從上到下,由左到右填入,即一棵完全二元樹。
三.優先權佇列在JDK中的實作方式
研究原始碼最好的方式是debug,看每一步變數的變化,我們可以簡單寫一個Demo,debug進源碼一探究竟:
#這裡我們簡單地創建一個優先隊列,向其中添加三個元素,我們可以在代碼第一行打一個斷點,如果您使用Eclipse#編輯器的話,接下來可以按F5進入原始碼:
程式碼運行到這裡,PriorityQueue呼叫自己的一個重載建構器,第一個參數是數組預設大小,第二個是元素比較的Comparator,我們這裡的Demo比較簡單,您在使用優先佇列時可以選擇實作自己的Comparator。
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) { // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = 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) //第一次添加元素,直接放到第0个位置即可 queue[0] = e; else //需要将元素放到最后,再做上滤操作 siftUp(i, e); return true; }
private void grow(int minCapacity) { int oldCapacity = queue.length; // Double size if small; else grow by 50% int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //元素拷贝 queue = Arrays.copyOf(queue, newCapacity);
註解也很清晰,首先判斷目前的陣列大小是否足夠小(<64),如果夠小則將大小擴充為2倍,否則原大小加上50%。要注意的是,這裡最後做了一個大小是否溢出的判斷。
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
private void siftUpUsingComparator(int k, E x) { while (k > 0) { //计算父亲节点的下标 int parent = (k - 1) >>> 1; Object e = queue[parent]; //与父节点进行比较 if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x; }
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 siftDownUsingComparator(int k, E x) { int half = size >>> 1; //这里k必须有孩子,故叶节点需要比较 while (k < half) { //以下几行代码到较小的那个儿子,用变量c表示 int child = (k << 1) + 1; //这里假设左儿子比较小 Object c = queue[child]; int right = child + 1; //左右儿子比较,如果右儿子小则将c赋值为右儿子 if (right < size && comparator.compare((E) c, (E) queue[right]) > 0) c = queue[child = right]; //如果x比小儿子还小,说明k就是正确位置 if (comparator.compare(x, (E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = x; }
以上是詳解優先隊列在JDK中的實作方式的詳細內容。更多資訊請關注PHP中文網其他相關文章!