rollup merge of #17355 : gamazeps/issue17210

[rust.git] / src / libcollections / priority_queue.rs

diff --git a/src/libcollections/priority_queue.rs b/src/libcollections/priority_queue.rs
index eedb61c0712de08193016fe49e1d041945c46bfd..68e2086d042a36e45789949d7c10c096bf79ab3c 100644 (file)
--- a/src/libcollections/priority_queue.rs
+++ b/src/libcollections/priority_queue.rs
@@ -10,6 +10,11 @@
 
 //! A priority queue implemented with a binary heap.
 //!
+//! Insertions have `O(log n)` time complexity and checking or popping the largest element is
+//! `O(1)`. Converting a vector to a priority queue can be done in-place, and has `O(n)`
+//! complexity. A priority queue can also be converted to a sorted vector in-place, allowing it to
+//! be used for an `O(n log n)` in-place heapsort.
+//!
 //! # Example
 //!
 //! This is a larger example which implements [Dijkstra's algorithm][dijkstra]
@@ -516,7 +521,7 @@ fn siftdown(&mut self, pos: uint) {
 }
 
 /// `PriorityQueue` iterator.
-pub struct Items <'a, T> {
+pub struct Items <'a, T:'a> {
     iter: slice::Items<'a, T>,
 }
 
@@ -529,10 +534,9 @@ fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 }
 
 impl<T: Ord> FromIterator<T> for PriorityQueue<T> {
-    fn from_iter<Iter: Iterator<T>>(iter: Iter) -> PriorityQueue<T> {
-        let mut q = PriorityQueue::new();
-        q.extend(iter);
-        q
+    fn from_iter<Iter: Iterator<T>>(mut iter: Iter) -> PriorityQueue<T> {
+        let vec: Vec<T> = iter.collect();
+        PriorityQueue::from_vec(vec)
     }
 }