001: /*
002: * Copyright 2007 Google Inc.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License"); you may not
005: * use this file except in compliance with the License. You may obtain a copy of
006: * the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
012: * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
013: * License for the specific language governing permissions and limitations under
014: * the License.
015: */
016: package java.util;
017:
018: /**
019: * An unbounded priority queue based on a priority heap. <a
020: * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/PriorityQueue.html">[Sun
021: * docs]</a>
022: *
023: * @param <E> element type.
024: */
025: public class PriorityQueue<E> extends AbstractQueue<E> {
026:
027: /**
028: * A heap held in an array. heap[0] is the root of the heap (the smallest
029: * element), the subtrees of node i are 2*i+1 (left) and 2*i+2 (right). Node i
030: * is a leaf node if 2*i>=n. Node i's parent, if i>0, is floor((i-1)/2).
031: */
032: private ArrayList<E> heap;
033: private Comparator<? super E> cmp;
034:
035: public PriorityQueue() {
036: this (11);
037: }
038:
039: public PriorityQueue(Collection<? extends E> c) {
040: this (c.size());
041: addAll(c);
042: }
043:
044: public PriorityQueue(int initialCapacity) {
045: this (initialCapacity, Comparators.natural());
046: }
047:
048: public PriorityQueue(int initialCapacity, Comparator<? super E> cmp) {
049: heap = new ArrayList<E>(initialCapacity);
050: this .cmp = cmp;
051: }
052:
053: public PriorityQueue(PriorityQueue<? extends E> c) {
054: // TODO(jat): better solution
055: this (c.size());
056: addAll(c);
057: }
058:
059: public PriorityQueue(SortedSet<? extends E> c) {
060: // TODO(jat): better solution
061: this (c.size());
062: addAll(c);
063: }
064:
065: @Override
066: public Iterator<E> iterator() {
067: // TODO(jat): perhaps a better way to do this
068: return Collections.unmodifiableList(heap).iterator();
069: }
070:
071: @Override
072: public boolean offer(E e) {
073: int node = heap.size();
074: heap.add(e);
075: while (node > 0) {
076: int childNode = node;
077: node = (node - 1) / 2; // get parent of current node
078: if (cmp.compare(heap.get(node), heap.get(childNode)) <= 0) {
079: // parent is smaller, so we have a valid heap
080: heap.set(childNode, e);
081: return true;
082: }
083: // exchange with parent and try again
084: heap.set(childNode, heap.get(node));
085: }
086: heap.set(node, e);
087: return true;
088: }
089:
090: @Override
091: public E peek() {
092: if (heap.size() == 0) {
093: return null;
094: }
095: return heap.get(0);
096: }
097:
098: @Override
099: public E poll() {
100: if (heap.size() == 0) {
101: return null;
102: }
103: E value = heap.get(0);
104: heap.set(0, heap.remove(heap.size() - 1)); // move last element to root
105: makeHeap(0); // make it back into a heap
106: return value;
107: }
108:
109: @Override
110: public int size() {
111: return heap.size();
112: }
113:
114: /**
115: * Make the subtree rooted at <code>node</code> a valid heap. O(n) time
116: *
117: * @param node
118: */
119: protected void makeHeap(int node) {
120: int n = heap.size();
121: if (2 * node >= n) {
122: // leaf node, no work to do
123: return;
124: }
125: makeHeap(2 * node + 1); // make left subtree a heap
126: makeHeap(2 * node + 2); // make right subtree a heap
127: mergeHeaps(node);
128: }
129:
130: /**
131: * Merge two subheaps into a single heap. O(log n) time
132: *
133: * PRECONDITION: both children of <code>node</code> are heaps
134: *
135: * @param node the parent of the two subtrees to merge
136: */
137: protected void mergeHeaps(int node) {
138: int n = heap.size();
139: E value = heap.get(node);
140: while (node * 2 < n) {
141: int childNode = 2 * node + 1; // start with left child
142: if ((childNode + 1 < n)
143: && (cmp.compare(heap.get(childNode + 1), heap
144: .get(childNode)) < 0)) {
145: childNode++; // right child is smaller, go down that path
146: }
147: heap.set(node, heap.get(childNode));
148: node = childNode;
149: }
150: heap.set(node, value);
151: }
152:
153: }
|