BinaryHeap


1   /*
2    *  Copyright 2001-2004 The Apache Software Foundation
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   */
16  package org.apache.commons.collections;
17  
18  import java.util.AbstractCollection  ;
19  import java.util.Comparator  ;
20  import java.util.Iterator  ;
21  import java.util.NoSuchElementException  ;
22  
23  /**
24   * Binary heap implementation of <code>PriorityQueue</code>.
25   * <p>
26   * The <code>PriorityQueue</code> interface has now been replaced for most uses
27   * by the <code>Buffer</code> interface. This class and the interface are
28   * retained for backwards compatibility. The intended replacement is
29   * {@link org.apache.commons.collections.buffer.PriorityBuffer PriorityBuffer}.
30   * <p>
31   * The removal order of a binary heap is based on either the natural sort
32   * order of its elements or a specified {@link Comparator}.  The 
33   * {@link #pop()} method always returns the first element as determined
34   * by the sort order.  (The <code>isMinHeap</code> flag in the constructors
35   * can be used to reverse the sort order, in which case {@link #pop()}
36   * will always remove the last element.)  The removal order is 
37   * <i>not</i> the same as the order of iteration; elements are
38   * returned by the iterator in no particular order.
39   * <p>
40   * The {@link #insert(Object)} and {@link #pop()} operations perform
41   * in logarithmic time.  The {@link #peek()} operation performs in constant
42   * time.  All other operations perform in linear time or worse.
43   * <p>
44   * Note that this implementation is not synchronized.  Use SynchronizedPriorityQueue
45   * to provide synchronized access to a <code>BinaryHeap</code>:
46   *
47   * <pre>
48   * PriorityQueue heap = new SynchronizedPriorityQueue(new BinaryHeap());
49   * </pre>
50   *
51   * @deprecated Replaced by PriorityBuffer in buffer subpackage.
52   *  Due to be removed in v4.0.
53   * @since Commons Collections 1.0
54   * @version $Revision: 1.24 $ $Date: 2004/02/18 01:15:42 $
55   * 
56   * @author Peter Donald
57   * @author Ram Chidambaram
58   * @author Michael A. Smith
59   * @author Paul Jack
60   * @author Stephen Colebourne
61   */
62  public final class BinaryHeap extends AbstractCollection  
63          implements PriorityQueue, Buffer {
64  
65      /**
66       * The default capacity for a binary heap.
67       */
68      private final static int DEFAULT_CAPACITY = 13;
69      /**
70       * The number of elements currently in this heap.
71       */
72      int m_size;  // package scoped for testing
73      /**
74       * The elements in this heap.
75       */
76      Object  [] m_elements;  // package scoped for testing
77      /**
78       * If true, the first element as determined by the sort order will 
79       * be returned.  If false, the last element as determined by the
80       * sort order will be returned.
81       */
82      boolean m_isMinHeap;  // package scoped for testing
83      /**
84       * The comparator used to order the elements
85       */
86      Comparator   m_comparator;  // package scoped for testing
87  
88      /**
89       * Constructs a new minimum binary heap.
90       */
91      public BinaryHeap() {
92          this(DEFAULT_CAPACITY, true);
93      }
94  
95      /**
96       * Constructs a new <code>BinaryHeap</code> that will use the given
97       * comparator to order its elements.
98       * 
99       * @param comparator  the comparator used to order the elements, null
100      *  means use natural order
101      */
102     public BinaryHeap(Comparator   comparator) {
103         this();
104         m_comparator = comparator;
105     }
106     
107     /**
108      * Constructs a new minimum binary heap with the specified initial capacity.
109      *  
110      * @param capacity  The initial capacity for the heap.  This value must
111      *  be greater than zero.
112      * @throws IllegalArgumentException  
113      *  if <code>capacity</code> is &lt;= <code>0</code>
114      */
115     public BinaryHeap(int capacity) {
116         this(capacity, true);
117     }
118 
119     /**
120      * Constructs a new <code>BinaryHeap</code>.
121      *
122      * @param capacity  the initial capacity for the heap
123      * @param comparator  the comparator used to order the elements, null
124      *  means use natural order
125      * @throws IllegalArgumentException  
126      *  if <code>capacity</code> is &lt;= <code>0</code>
127      */
128     public BinaryHeap(int capacity, Comparator   comparator) {
129         this(capacity);
130         m_comparator = comparator;
131     }
132 
133     /**
134      * Constructs a new minimum or maximum binary heap
135      *
136      * @param isMinHeap  if <code>true</code> the heap is created as a 
137      * minimum heap; otherwise, the heap is created as a maximum heap
138      */
139     public BinaryHeap(boolean isMinHeap) {
140         this(DEFAULT_CAPACITY, isMinHeap);
141     }
142 
143     /**
144      * Constructs a new <code>BinaryHeap</code>.
145      *
146      * @param isMinHeap  true to use the order imposed by the given 
147      *   comparator; false to reverse that order
148      * @param comparator  the comparator used to order the elements, null
149      *  means use natural order
150      */
151     public BinaryHeap(boolean isMinHeap, Comparator   comparator) {
152         this(isMinHeap);
153         m_comparator = comparator;
154     }
155 
156     /**
157      * Constructs a new minimum or maximum binary heap with the specified 
158      * initial capacity.
159      *
160      * @param capacity the initial capacity for the heap.  This value must 
161      * be greater than zero.
162      * @param isMinHeap if <code>true</code> the heap is created as a 
163      *  minimum heap; otherwise, the heap is created as a maximum heap.
164      * @throws IllegalArgumentException 
165      *  if <code>capacity</code> is <code>&lt;= 0</code>
166      */
167     public BinaryHeap(int capacity, boolean isMinHeap) {
168         if (capacity <= 0) {
169             throw new IllegalArgumentException  ("invalid capacity");
170         }
171         m_isMinHeap = isMinHeap;
172 
173         //+1 as 0 is noop
174         m_elements = new Object  [capacity + 1];
175     }
176 
177     /**
178      * Constructs a new <code>BinaryHeap</code>.
179      *
180      * @param capacity  the initial capacity for the heap
181      * @param isMinHeap  true to use the order imposed by the given 
182      *   comparator; false to reverse that order
183      * @param comparator  the comparator used to order the elements, null
184      *  means use natural order
185      * @throws IllegalArgumentException 
186      *  if <code>capacity</code> is <code>&lt;= 0</code>
187      */
188     public BinaryHeap(int capacity, boolean isMinHeap, Comparator   comparator) {
189         this(capacity, isMinHeap);
190         m_comparator = comparator;
191     }
192 
193     //-----------------------------------------------------------------------
194     /**
195      * Clears all elements from queue.
196      */
197     public void clear() {
198         m_elements = new Object  [m_elements.length];  // for gc
199         m_size = 0;
200     }
201 
202     /**
203      * Tests if queue is empty.
204      *
205      * @return <code>true</code> if queue is empty; <code>false</code> 
206      *  otherwise.
207      */
208     public boolean isEmpty() {
209         return m_size == 0;
210     }
211 
212     /**
213      * Tests if queue is full.
214      *
215      * @return <code>true</code> if queue is full; <code>false</code>
216      *  otherwise.
217      */
218     public boolean isFull() {
219         //+1 as element 0 is noop
220         return m_elements.length == m_size + 1;
221     }
222 
223     /**
224      * Inserts an element into queue.
225      *
226      * @param element  the element to be inserted
227      */
228     public void insert(Object   element) {
229         if (isFull()) {
230             grow();
231         }
232         //percolate element to it's place in tree
233         if (m_isMinHeap) {
234             percolateUpMinHeap(element);
235         } else {
236             percolateUpMaxHeap(element);
237         }
238     }
239 
240     /**
241      * Returns the element on top of heap but don't remove it.
242      *
243      * @return the element at top of heap
244      * @throws NoSuchElementException  if <code>isEmpty() == true</code>
245      */
246     public Object   peek() throws NoSuchElementException   {
247         if (isEmpty()) {
248             throw new NoSuchElementException  ();
249         } else {
250             return m_elements[1];
251         }
252     }
253 
254     /**
255      * Returns the element on top of heap and remove it.
256      *
257      * @return the element at top of heap
258      * @throws NoSuchElementException  if <code>isEmpty() == true</code>
259      */
260     public Object   pop() throws NoSuchElementException   {
261         final Object   result = peek();
262         m_elements[1] = m_elements[m_size--];
263 
264         // set the unused element to 'null' so that the garbage collector
265         // can free the object if not used anywhere else.(remove reference)
266         m_elements[m_size + 1] = null;
267 
268         if (m_size != 0) {
269             // percolate top element to it's place in tree
270             if (m_isMinHeap) {
271                 percolateDownMinHeap(1);
272             } else {
273                 percolateDownMaxHeap(1);
274             }
275         }
276 
277         return result;
278     }
279 
280     /**
281      * Percolates element down heap from the position given by the index.
282      * <p>
283      * Assumes it is a minimum heap.
284      *
285      * @param index the index for the element
286      */
287     protected void percolateDownMinHeap(final int index) {
288         final Object   element = m_elements[index];
289         int hole = index;
290 
291         while ((hole * 2) <= m_size) {
292             int child = hole * 2;
293 
294             // if we have a right child and that child can not be percolated
295             // up then move onto other child
296             if (child != m_size && compare(m_elements[child + 1], m_elements[child]) < 0) {
297                 child++;
298             }
299 
300             // if we found resting place of bubble then terminate search
301             if (compare(m_elements[child], element) >= 0) {
302                 break;
303             }
304 
305             m_elements[hole] = m_elements[child];
306             hole = child;
307         }
308 
309         m_elements[hole] = element;
310     }
311 
312     /**
313      * Percolates element down heap from the position given by the index.
314      * <p>
315      * Assumes it is a maximum heap.
316      *
317      * @param index the index of the element
318      */
319     protected void percolateDownMaxHeap(final int index) {
320         final Object   element = m_elements[index];
321         int hole = index;
322 
323         while ((hole * 2) <= m_size) {
324             int child = hole * 2;
325 
326             // if we have a right child and that child can not be percolated
327             // up then move onto other child
328             if (child != m_size && compare(m_elements[child + 1], m_elements[child]) > 0) {
329                 child++;
330             }
331 
332             // if we found resting place of bubble then terminate search
333             if (compare(m_elements[child], element) <= 0) {
334                 break;
335             }
336 
337             m_elements[hole] = m_elements[child];
338             hole = child;
339         }
340 
341         m_elements[hole] = element;
342     }
343 
344     /**
345      * Percolates element up heap from the position given by the index.
346      * <p>
347      * Assumes it is a minimum heap.
348      *
349      * @param index the index of the element to be percolated up
350      */
351     protected void percolateUpMinHeap(final int index) {
352         int hole = index;
353         Object   element = m_elements[hole];
354         while (hole > 1 && compare(element, m_elements[hole / 2]) < 0) {
355             // save element that is being pushed down
356             // as the element "bubble" is percolated up
357             final int next = hole / 2;
358             m_elements[hole] = m_elements[next];
359             hole = next;
360         }
361         m_elements[hole] = element;
362     }
363 
364     /**
365      * Percolates a new element up heap from the bottom.
366      * <p>
367      * Assumes it is a minimum heap.
368      *
369      * @param element the element
370      */
371     protected void percolateUpMinHeap(final Object   element) {
372         m_elements[++m_size] = element;
373         percolateUpMinHeap(m_size);
374     }
375 
376     /**
377      * Percolates element up heap from from the position given by the index.
378      * <p>
379      * Assume it is a maximum heap.
380      *
381      * @param index the index of the element to be percolated up
382      */
383     protected void percolateUpMaxHeap(final int index) {
384         int hole = index;
385         Object   element = m_elements[hole];
386         
387         while (hole > 1 && compare(element, m_elements[hole / 2]) > 0) {
388             // save element that is being pushed down
389             // as the element "bubble" is percolated up
390             final int next = hole / 2;
391             m_elements[hole] = m_elements[next];
392             hole = next;
393         }
394 
395         m_elements[hole] = element;
396     }
397     
398     /**
399      * Percolates a new element up heap from the bottom.
400      * <p>
401      * Assume it is a maximum heap.
402      *
403      * @param element the element
404      */
405     protected void percolateUpMaxHeap(final Object   element) {
406         m_elements[++m_size] = element;
407         percolateUpMaxHeap(m_size);
408     }
409     
410     /**
411      * Compares two objects using the comparator if specified, or the
412      * natural order otherwise.
413      * 
414      * @param a  the first object
415      * @param b  the second object
416      * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
417      */
418     private int compare(Object   a, Object   b) {
419         if (m_comparator != null) {
420             return m_comparator.compare(a, b);
421         } else {
422             return ((Comparable  ) a).compareTo(b);
423         }
424     }
425 
426     /**
427      * Increases the size of the heap to support additional elements
428      */
429     protected void grow() {
430         final Object  [] elements = new Object  [m_elements.length * 2];
431         System.arraycopy(m_elements, 0, elements, 0, m_elements.length);
432         m_elements = elements;
433     }
434 
435     /**
436      * Returns a string representation of this heap.  The returned string
437      * is similar to those produced by standard JDK collections.
438      *
439      * @return a string representation of this heap
440      */
441     public String   toString() {
442         final StringBuffer   sb = new StringBuffer  ();
443 
444         sb.append("[ ");
445 
446         for (int i = 1; i < m_size + 1; i++) {
447             if (i != 1) {
448                 sb.append(", ");
449             }
450             sb.append(m_elements[i]);
451         }
452 
453         sb.append(" ]");
454 
455         return sb.toString();
456     }
457 
458 
459     /**
460      * Returns an iterator over this heap's elements.
461      *
462      * @return an iterator over this heap's elements
463      */
464     public Iterator   iterator() {
465         return new Iterator  () {
466 
467             private int index = 1;
468             private int lastReturnedIndex = -1;
469 
470             public boolean hasNext() {
471                 return index <= m_size;
472             }
473 
474             public Object   next() {
475                 if (!hasNext()) throw new NoSuchElementException  ();
476                 lastReturnedIndex = index;
477                 index++;
478                 return m_elements[lastReturnedIndex];
479             }
480 
481             public void remove() {
482                 if (lastReturnedIndex == -1) {
483                     throw new IllegalStateException  ();
484                 }
485                 m_elements[ lastReturnedIndex ] = m_elements[ m_size ];
486                 m_elements[ m_size ] = null;
487                 m_size--;  
488                 if( m_size != 0 && lastReturnedIndex <= m_size) {
489                     int compareToParent = 0;
490                     if (lastReturnedIndex > 1) {
491                         compareToParent = compare(m_elements[lastReturnedIndex], 
492                             m_elements[lastReturnedIndex / 2]);  
493                     }
494                     if (m_isMinHeap) {
495                         if (lastReturnedIndex > 1 && compareToParent < 0) {
496                             percolateUpMinHeap(lastReturnedIndex); 
497                         } else {
498                             percolateDownMinHeap(lastReturnedIndex);
499                         }
500                     } else {  // max heap
501                         if (lastReturnedIndex > 1 && compareToParent > 0) {
502                             percolateUpMaxHeap(lastReturnedIndex); 
503                         } else {
504                             percolateDownMaxHeap(lastReturnedIndex);
505                         }
506                     }          
507                 }
508                 index--;
509                 lastReturnedIndex = -1; 
510             }
511 
512         };
513     }
514 
515 
516     /**
517      * Adds an object to this heap. Same as {@link #insert(Object)}.
518      *
519      * @param object  the object to add
520      * @return true, always
521      */
522     public boolean add(Object   object) {
523         insert(object);
524         return true;
525     }
526 
527     /**
528      * Returns the priority element. Same as {@link #peek()}.
529      *
530      * @return the priority element
531      * @throws BufferUnderflowException if this heap is empty
532      */
533     public Object   get() {
534         try {
535             return peek();
536         } catch (NoSuchElementException   e) {
537             throw new BufferUnderflowException();
538         }
539     }
540 
541     /**
542      * Removes the priority element. Same as {@link #pop()}.
543      *
544      * @return the removed priority element
545      * @throws BufferUnderflowException if this heap is empty
546      */
547     public Object   remove() {
548         try {
549             return pop();
550         } catch (NoSuchElementException   e) {
551             throw new BufferUnderflowException();
552         }
553     }
554 
555     /**
556      * Returns the number of elements in this heap.
557      *
558      * @return the number of elements in this heap
559      */
560     public int size() {
561         return m_size;
562     }
563 
564 }
565
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags