← Back to branch summary

~ubuntu-branches/ubuntu/saucy/golang/saucy

« back to all changes in this revision

Viewing changes to src/pkg/container/heap/heap.go

  • Committer: Package Import Robot
  • Author(s): Adam Conrad
  • Date: 2013-07-08 05:52:37 UTC
  • mfrom: (29.1.1 sid)
  • Revision ID: package-import@ubuntu.com-20130708055237-at01839e0hp8z3ni
Tags: 2:1.1-1ubuntu1
016-armhf-elf-header.patch: Use correct ELF header for armhf binaries.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/container/heap/heap.go
4
4
 
5
5
// Package heap provides heap operations for any type that implements
6
6
// heap.Interface. A heap is a tree with the property that each node is the
7
 
// highest-valued node in its subtree.
 
7
// minimum-valued node in its subtree.
8
8
//
9
9
// A heap is a common way to implement a priority queue. To build a priority
10
10
// queue, implement the Heap interface with the (negative) priority as the
11
11
// ordering for the Less method, so Push adds items while Pop removes the
12
12
// highest-priority item from the queue. The Examples include such an
13
 
// implementation; the file example_test.go has the complete source.
 
13
// implementation; the file example_pq_test.go has the complete source.
14
14
//
15
15
package heap
16
16
 
79
79
func up(h Interface, j int) {
80
80
        for {
81
81
                i := (j - 1) / 2 // parent
82
 
                if i == j || h.Less(i, j) {
 
82
                if i == j || !h.Less(j, i) {
83
83
                        break
84
84
                }
85
85
                h.Swap(i, j)
90
90
func down(h Interface, i, n int) {
91
91
        for {
92
92
                j1 := 2*i + 1
93
 
                if j1 >= n {
 
93
                if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
94
94
                        break
95
95
                }
96
96
                j := j1 // left child
97
97
                if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) {
98
98
                        j = j2 // = 2*i + 2  // right child
99
99
                }
100
 
                if h.Less(i, j) {
 
100
                if !h.Less(j, i) {
101
101
                        break
102
102
                }
103
103
                h.Swap(i, j)