diff options
| author | bors <bors@rust-lang.org> | 2014-12-02 02:52:15 +0000 |
|---|---|---|
| committer | bors <bors@rust-lang.org> | 2014-12-02 02:52:15 +0000 |
| commit | 8a210af7e56a7ad25310b482c84bdcba0e65666b (patch) | |
| tree | 286861beb2de9cd95e02302d1729d81d4a5a7548 | |
| parent | 5484d6f6d2844e9c52d42db52a1ba94739e10996 (diff) | |
| parent | 0212dff902da3d50123b6dc02fa0da250ddc0da4 (diff) | |
| download | rust-8a210af7e56a7ad25310b482c84bdcba0e65666b.tar.gz rust-8a210af7e56a7ad25310b482c84bdcba0e65666b.zip | |
auto merge of #19450 : jbapple/rust/pq-pop-time, r=Gankro
pop calls siftdown, siftdown calls siftdown_range, and siftdown_range loops on an index that can start as low as 0 and approximately doubles each iteration.
| -rw-r--r-- | src/libcollections/binary_heap.rs | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/src/libcollections/binary_heap.rs b/src/libcollections/binary_heap.rs index cbf45ee36a3..330b9392974 100644 --- a/src/libcollections/binary_heap.rs +++ b/src/libcollections/binary_heap.rs @@ -10,8 +10,8 @@ //! 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)` +//! Insertion and popping the largest element have `O(log n)` time complexity. Checking 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. //! |