OLD | NEW |
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 Loading... |
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 } |
OLD | NEW |