Imported Upstream version 1.1~hg20130304upstream/1.1_hg20130304

1 files changed, 5 insertions, 5 deletions

diff --git a/src/pkg/container/heap/heap.go b/src/pkg/container/heap/heap.go
index 67018e6ba..c37e50e3c 100644
--- a/src/pkg/container/heap/heap.go
+++ b/src/pkg/container/heap/heap.go
@@ -4,13 +4,13 @@
 
 // Package heap provides heap operations for any type that implements
 // heap.Interface. A heap is a tree with the property that each node is the
-// highest-valued node in its subtree.
+// minimum-valued node in its subtree.
 //
 // A heap is a common way to implement a priority queue. To build a priority
 // queue, implement the Heap interface with the (negative) priority as the
 // ordering for the Less method, so Push adds items while Pop removes the
 // highest-priority item from the queue. The Examples include such an
-// implementation; the file example_test.go has the complete source.
+// implementation; the file example_pq_test.go has the complete source.
 //
 package heap
 
@@ -79,7 +79,7 @@ func Remove(h Interface, i int) interface{} {
 func up(h Interface, j int) {
 	for {
 		i := (j - 1) / 2 // parent
-		if i == j || h.Less(i, j) {
+		if i == j || !h.Less(j, i) {
 			break
 		}
 		h.Swap(i, j)
@@ -90,14 +90,14 @@ func up(h Interface, j int) {
 func down(h Interface, i, n int) {
 	for {
 		j1 := 2*i + 1
-		if j1 >= n {
+		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
 			break
 		}
 		j := j1 // left child
 		if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) {
 			j = j2 // = 2*i + 2  // right child
 		}
-		if h.Less(i, j) {
+		if !h.Less(j, i) {
 			break
 		}
 		h.Swap(i, j)