PriorityQueue.java
上传用户:quxuerui
上传日期:2018-01-08
资源大小:41811k
文件大小:4k
源码类别:

网格计算

开发平台:

Java

  1. /**
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *     http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.hadoop.util;
  18. /** A PriorityQueue maintains a partial ordering of its elements such that the
  19.   least element can always be found in constant time.  Put()'s and pop()'s
  20.   require log(size) time. */
  21. public abstract class PriorityQueue<T> {
  22.   private T[] heap;
  23.   private int size;
  24.   private int maxSize;
  25.   /** Determines the ordering of objects in this priority queue.  Subclasses
  26.       must define this one method. */
  27.   protected abstract boolean lessThan(Object a, Object b);
  28.   /** Subclass constructors must call this. */
  29.   @SuppressWarnings("unchecked")
  30.   protected final void initialize(int maxSize) {
  31.     size = 0;
  32.     int heapSize = maxSize + 1;
  33.     heap = (T[]) new Object[heapSize];
  34.     this.maxSize = maxSize;
  35.   }
  36.   /**
  37.    * Adds an Object to a PriorityQueue in log(size) time.
  38.    * If one tries to add more objects than maxSize from initialize
  39.    * a RuntimeException (ArrayIndexOutOfBound) is thrown.
  40.    */
  41.   public final void put(T element) {
  42.     size++;
  43.     heap[size] = element;
  44.     upHeap();
  45.   }
  46.   /**
  47.    * Adds element to the PriorityQueue in log(size) time if either
  48.    * the PriorityQueue is not full, or not lessThan(element, top()).
  49.    * @param element
  50.    * @return true if element is added, false otherwise.
  51.    */
  52.   public boolean insert(T element){
  53.     if (size < maxSize){
  54.       put(element);
  55.       return true;
  56.     }
  57.     else if (size > 0 && !lessThan(element, top())){
  58.       heap[1] = element;
  59.       adjustTop();
  60.       return true;
  61.     }
  62.     else
  63.       return false;
  64.   }
  65.   /** Returns the least element of the PriorityQueue in constant time. */
  66.   public final T top() {
  67.     if (size > 0)
  68.       return heap[1];
  69.     else
  70.       return null;
  71.   }
  72.   /** Removes and returns the least element of the PriorityQueue in log(size)
  73.       time. */
  74.   public final T pop() {
  75.     if (size > 0) {
  76.       T result = heap[1];   // save first value
  77.       heap[1] = heap[size];   // move last to first
  78.       heap[size] = null;   // permit GC of objects
  79.       size--;
  80.       downHeap();   // adjust heap
  81.       return result;
  82.     } else
  83.       return null;
  84.   }
  85.   /** Should be called when the Object at top changes values.  Still log(n)
  86.    * worst case, but it's at least twice as fast to <pre>
  87.    *  { pq.top().change(); pq.adjustTop(); }
  88.    * </pre> instead of <pre>
  89.    *  { o = pq.pop(); o.change(); pq.push(o); }
  90.    * </pre>
  91.    */
  92.   public final void adjustTop() {
  93.     downHeap();
  94.   }
  95.   /** Returns the number of elements currently stored in the PriorityQueue. */
  96.   public final int size() {
  97.     return size;
  98.   }
  99.   /** Removes all entries from the PriorityQueue. */
  100.   public final void clear() {
  101.     for (int i = 0; i <= size; i++)
  102.       heap[i] = null;
  103.     size = 0;
  104.   }
  105.   private final void upHeap() {
  106.     int i = size;
  107.     T node = heap[i];   // save bottom node
  108.     int j = i >>> 1;
  109.     while (j > 0 && lessThan(node, heap[j])) {
  110.       heap[i] = heap[j];   // shift parents down
  111.       i = j;
  112.       j = j >>> 1;
  113.     }
  114.     heap[i] = node;   // install saved node
  115.   }
  116.   private final void downHeap() {
  117.     int i = 1;
  118.     T node = heap[i];   // save top node
  119.     int j = i << 1;   // find smaller child
  120.     int k = j + 1;
  121.     if (k <= size && lessThan(heap[k], heap[j])) {
  122.       j = k;
  123.     }
  124.     while (j <= size && lessThan(heap[j], node)) {
  125.       heap[i] = heap[j];   // shift up child
  126.       i = j;
  127.       j = i << 1;
  128.       k = j + 1;
  129.       if (k <= size && lessThan(heap[k], heap[j])) {
  130. j = k;
  131.       }
  132.     }
  133.     heap[i] = node;   // install saved node
  134.   }
  135. }