Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(1858)

Side by Side Diff: src/pkg/container/heap/heap.go

Issue 6613064: code review 6613064: container/heap: optimization in case heap has many dupl... (Closed)
Patch Set: diff -r c3570e8ed478 https://go.googlecode.com/hg/ Created 11 years, 5 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | src/pkg/container/heap/heap_test.go » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2009 The Go Authors. All rights reserved. 1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style 2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file. 3 // license that can be found in the LICENSE file.
4 4
5 // Package heap provides heap operations for any type that implements 5 // Package heap provides heap operations for any type that implements
6 // heap.Interface. A heap is a tree with the property that each node is the 6 // heap.Interface. A heap is a tree with the property that each node is the
7 // highest-valued node in its subtree. 7 // highest-valued node in its subtree.
8 // 8 //
9 // A heap is a common way to implement a priority queue. To build a priority 9 // A heap is a common way to implement a priority queue. To build a priority
10 // queue, implement the Heap interface with the (negative) priority as the 10 // queue, implement the Heap interface with the (negative) priority as the
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after
72 h.Swap(i, n) 72 h.Swap(i, n)
73 down(h, i, n) 73 down(h, i, n)
74 up(h, i) 74 up(h, i)
75 } 75 }
76 return h.Pop() 76 return h.Pop()
77 } 77 }
78 78
79 func up(h Interface, j int) { 79 func up(h Interface, j int) {
80 for { 80 for {
81 i := (j - 1) / 2 // parent 81 i := (j - 1) / 2 // parent
82 » » if i == j || h.Less(i, j) { 82 » » if i == j || !h.Less(j, i) {
83 break 83 break
84 } 84 }
85 h.Swap(i, j) 85 h.Swap(i, j)
86 j = i 86 j = i
87 } 87 }
88 } 88 }
89 89
90 func down(h Interface, i, n int) { 90 func down(h Interface, i, n int) {
91 for { 91 for {
92 j1 := 2*i + 1 92 j1 := 2*i + 1
93 if j1 >= n { 93 if j1 >= n {
94 break 94 break
95 } 95 }
96 j := j1 // left child 96 j := j1 // left child
97 if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) { 97 if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) {
98 j = j2 // = 2*i + 2 // right child 98 j = j2 // = 2*i + 2 // right child
99 } 99 }
100 » » if h.Less(i, j) { 100 » » if !h.Less(j, i) {
101 break 101 break
102 } 102 }
103 h.Swap(i, j) 103 h.Swap(i, j)
104 i = j 104 i = j
105 } 105 }
106 } 106 }
OLDNEW
« no previous file with comments | « no previous file | src/pkg/container/heap/heap_test.go » ('j') | no next file with comments »

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b