70 *
71 * <p>Implementation note: this implementation provides
72 * O(log(n)) time for the enqueuing and dequeuing methods
73 * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
74 * linear time for the {@code remove(Object)} and {@code contains(Object)}
75 * methods; and constant time for the retrieval methods
76 * ({@code peek}, {@code element}, and {@code size}).
77 *
78 * <p>This class is a member of the
79 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
80 * Java Collections Framework</a>.
81 *
82 * @since 1.5
83 * @author Josh Bloch, Doug Lea
84 * @param <E> the type of elements held in this queue
85 */
86 @SuppressWarnings("unchecked")
87 public class PriorityQueue<E> extends AbstractQueue<E>
88 implements java.io.Serializable {
89
90 private static final long serialVersionUID = -7720805057305804111L;
91
92 private static final int DEFAULT_INITIAL_CAPACITY = 11;
93
94 /**
95 * Priority queue represented as a balanced binary heap: the two
96 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
97 * priority queue is ordered by comparator, or by the elements'
98 * natural ordering, if comparator is null: For each node n in the
99 * heap and each descendant d of n, n <= d. The element with the
100 * lowest value is in queue[0], assuming the queue is nonempty.
101 */
102 transient Object[] queue; // non-private to simplify nested class access
103
104 /**
105 * The number of elements in the priority queue.
106 */
107 int size;
108
109 /**
738 * queue, or {@code null} if this queue is sorted according to
739 * the {@linkplain Comparable natural ordering} of its elements.
740 *
741 * @return the comparator used to order this queue, or
742 * {@code null} if this queue is sorted according to the
743 * natural ordering of its elements
744 */
745 public Comparator<? super E> comparator() {
746 return comparator;
747 }
748
749 /**
750 * Saves this queue to a stream (that is, serializes it).
751 *
752 * @param s the stream
753 * @throws java.io.IOException if an I/O error occurs
754 * @serialData The length of the array backing the instance is
755 * emitted (int), followed by all of its elements
756 * (each an {@code Object}) in the proper order.
757 */
758 private void writeObject(java.io.ObjectOutputStream s)
759 throws java.io.IOException {
760 // Write out element count, and any hidden stuff
761 s.defaultWriteObject();
762
763 // Write out array length, for compatibility with 1.5 version
764 s.writeInt(Math.max(2, size + 1));
765
766 // Write out all elements in the "proper order".
767 final Object[] es = queue;
768 for (int i = 0, n = size; i < n; i++)
769 s.writeObject(es[i]);
770 }
771
772 /**
773 * Reconstitutes the {@code PriorityQueue} instance from a stream
774 * (that is, deserializes it).
775 *
776 * @param s the stream
777 * @throws ClassNotFoundException if the class of a serialized object
778 * could not be found
779 * @throws java.io.IOException if an I/O error occurs
780 */
781 private void readObject(java.io.ObjectInputStream s)
782 throws java.io.IOException, ClassNotFoundException {
783 // Read in size, and any hidden stuff
784 s.defaultReadObject();
785
786 // Read in (and discard) array length
787 s.readInt();
788
789 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
790 final Object[] es = queue = new Object[Math.max(size, 1)];
791
792 // Read in all elements.
793 for (int i = 0, n = size; i < n; i++)
794 es[i] = s.readObject();
795
796 // Elements are guaranteed to be in "proper order", but the
797 // spec has never explained what that might be.
798 heapify();
799 }
800
|
70 *
71 * <p>Implementation note: this implementation provides
72 * O(log(n)) time for the enqueuing and dequeuing methods
73 * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
74 * linear time for the {@code remove(Object)} and {@code contains(Object)}
75 * methods; and constant time for the retrieval methods
76 * ({@code peek}, {@code element}, and {@code size}).
77 *
78 * <p>This class is a member of the
79 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
80 * Java Collections Framework</a>.
81 *
82 * @since 1.5
83 * @author Josh Bloch, Doug Lea
84 * @param <E> the type of elements held in this queue
85 */
86 @SuppressWarnings("unchecked")
87 public class PriorityQueue<E> extends AbstractQueue<E>
88 implements java.io.Serializable {
89
90 @java.io.Serial
91 private static final long serialVersionUID = -7720805057305804111L;
92
93 private static final int DEFAULT_INITIAL_CAPACITY = 11;
94
95 /**
96 * Priority queue represented as a balanced binary heap: the two
97 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
98 * priority queue is ordered by comparator, or by the elements'
99 * natural ordering, if comparator is null: For each node n in the
100 * heap and each descendant d of n, n <= d. The element with the
101 * lowest value is in queue[0], assuming the queue is nonempty.
102 */
103 transient Object[] queue; // non-private to simplify nested class access
104
105 /**
106 * The number of elements in the priority queue.
107 */
108 int size;
109
110 /**
739 * queue, or {@code null} if this queue is sorted according to
740 * the {@linkplain Comparable natural ordering} of its elements.
741 *
742 * @return the comparator used to order this queue, or
743 * {@code null} if this queue is sorted according to the
744 * natural ordering of its elements
745 */
746 public Comparator<? super E> comparator() {
747 return comparator;
748 }
749
750 /**
751 * Saves this queue to a stream (that is, serializes it).
752 *
753 * @param s the stream
754 * @throws java.io.IOException if an I/O error occurs
755 * @serialData The length of the array backing the instance is
756 * emitted (int), followed by all of its elements
757 * (each an {@code Object}) in the proper order.
758 */
759 @java.io.Serial
760 private void writeObject(java.io.ObjectOutputStream s)
761 throws java.io.IOException {
762 // Write out element count, and any hidden stuff
763 s.defaultWriteObject();
764
765 // Write out array length, for compatibility with 1.5 version
766 s.writeInt(Math.max(2, size + 1));
767
768 // Write out all elements in the "proper order".
769 final Object[] es = queue;
770 for (int i = 0, n = size; i < n; i++)
771 s.writeObject(es[i]);
772 }
773
774 /**
775 * Reconstitutes the {@code PriorityQueue} instance from a stream
776 * (that is, deserializes it).
777 *
778 * @param s the stream
779 * @throws ClassNotFoundException if the class of a serialized object
780 * could not be found
781 * @throws java.io.IOException if an I/O error occurs
782 */
783 @java.io.Serial
784 private void readObject(java.io.ObjectInputStream s)
785 throws java.io.IOException, ClassNotFoundException {
786 // Read in size, and any hidden stuff
787 s.defaultReadObject();
788
789 // Read in (and discard) array length
790 s.readInt();
791
792 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
793 final Object[] es = queue = new Object[Math.max(size, 1)];
794
795 // Read in all elements.
796 for (int i = 0, n = size; i < n; i++)
797 es[i] = s.readObject();
798
799 // Elements are guaranteed to be in "proper order", but the
800 // spec has never explained what that might be.
801 heapify();
802 }
803
|