diff options
author | Sina Siadat <siadat@gmail.com> | 2016-06-21 00:54:52 +0430 |
---|---|---|
committer | Robert Griesemer <gri@golang.org> | 2016-08-16 00:40:03 +0000 |
commit | b98d8cd5ce0c279674472af247d86f8c0b73828a (patch) | |
tree | 6217d40271ac9967567318cd647677291257ea8d /src/container | |
parent | b5e43e669a5e1591c9a6c7157b4dd0d2796d3037 (diff) | |
download | go-b98d8cd5ce0c279674472af247d86f8c0b73828a.tar.gz go-b98d8cd5ce0c279674472af247d86f8c0b73828a.zip |
container/heap: remove one unnecessary comparison in Fix
The heap.Fix function calls both down and up. If the element is moved
down, we don't need to call up and we could save a comparison.
(per suggestion by Radu Berinde)
Fixes #16098.
Change-Id: I83a74710e66cf0d274d8c0743338c26f89f31afe
Reviewed-on: https://go-review.googlesource.com/24273
Reviewed-by: Robert Griesemer <gri@golang.org>
Diffstat (limited to 'src/container')
-rw-r--r-- | src/container/heap/heap.go | 9 |
1 files changed, 6 insertions, 3 deletions
diff --git a/src/container/heap/heap.go b/src/container/heap/heap.go index 5fe23b9537..7110c513f0 100644 --- a/src/container/heap/heap.go +++ b/src/container/heap/heap.go @@ -83,8 +83,9 @@ func Remove(h Interface, i int) interface{} { // but less expensive than, calling Remove(h, i) followed by a Push of the new value. // The complexity is O(log(n)) where n = h.Len(). func Fix(h Interface, i int) { - down(h, i, h.Len()) - up(h, i) + if !down(h, i, h.Len()) { + up(h, i) + } } func up(h Interface, j int) { @@ -98,7 +99,8 @@ func up(h Interface, j int) { } } -func down(h Interface, i, n int) { +func down(h Interface, i0, n int) bool { + i := i0 for { j1 := 2*i + 1 if j1 >= n || j1 < 0 { // j1 < 0 after int overflow @@ -114,4 +116,5 @@ func down(h Interface, i, n int) { h.Swap(i, j) i = j } + return i > i0 } |