diff options
author | ltnwgl <ltnwgl@gmail.com> | 2017-03-24 11:55:22 +0800 |
---|---|---|
committer | Robert Griesemer <gri@golang.org> | 2017-05-09 03:38:37 +0000 |
commit | f5352a7763c8f96f7f092990d64339eae0623263 (patch) | |
tree | 369c9fa202fe2e09dea3f93210ce093d29e4f27a /src/container | |
parent | 716761b8b13926ef4a82dcb4ffc324066779239c (diff) | |
download | go-f5352a7763c8f96f7f092990d64339eae0623263.tar.gz go-f5352a7763c8f96f7f092990d64339eae0623263.zip |
container/heap: optimization when selecting smaller child
In down(), if two children are equal, we can choose either one.
Inspired by https://codereview.appspot.com/6613064/
Change-Id: Iaad4ca5e2f5111bf3abb87f606584e7d274c620b
Reviewed-on: https://go-review.googlesource.com/38612
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Diffstat (limited to 'src/container')
-rw-r--r-- | src/container/heap/heap.go | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/src/container/heap/heap.go b/src/container/heap/heap.go index 7110c513f0..af05261c10 100644 --- a/src/container/heap/heap.go +++ b/src/container/heap/heap.go @@ -107,7 +107,7 @@ func down(h Interface, i0, n int) bool { break } j := j1 // left child - if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) { + if j2 := j1 + 1; j2 < n && h.Less(j2, j1) { j = j2 // = 2*i + 2 // right child } if !h.Less(j, i) { |