diff options
Diffstat (limited to 'gcc-4.8.1/libgo/go/container/heap/heap.go')
-rw-r--r-- | gcc-4.8.1/libgo/go/container/heap/heap.go | 106 |
1 files changed, 0 insertions, 106 deletions
diff --git a/gcc-4.8.1/libgo/go/container/heap/heap.go b/gcc-4.8.1/libgo/go/container/heap/heap.go deleted file mode 100644 index bbaf40a98..000000000 --- a/gcc-4.8.1/libgo/go/container/heap/heap.go +++ /dev/null @@ -1,106 +0,0 @@ -// Copyright 2009 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// 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. -// -// 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. -// -package heap - -import "sort" - -// Any type that implements heap.Interface may be used as a -// min-heap with the following invariants (established after -// Init has been called or if the data is empty or sorted): -// -// !h.Less(j, i) for 0 <= i < h.Len() and j = 2*i+1 or 2*i+2 and j < h.Len() -// -// Note that Push and Pop in this interface are for package heap's -// implementation to call. To add and remove things from the heap, -// use heap.Push and heap.Pop. -type Interface interface { - sort.Interface - Push(x interface{}) // add x as element Len() - Pop() interface{} // remove and return element Len() - 1. -} - -// A heap must be initialized before any of the heap operations -// can be used. Init is idempotent with respect to the heap invariants -// and may be called whenever the heap invariants may have been invalidated. -// Its complexity is O(n) where n = h.Len(). -// -func Init(h Interface) { - // heapify - n := h.Len() - for i := n/2 - 1; i >= 0; i-- { - down(h, i, n) - } -} - -// Push pushes the element x onto the heap. The complexity is -// O(log(n)) where n = h.Len(). -// -func Push(h Interface, x interface{}) { - h.Push(x) - up(h, h.Len()-1) -} - -// Pop removes the minimum element (according to Less) from the heap -// and returns it. The complexity is O(log(n)) where n = h.Len(). -// Same as Remove(h, 0). -// -func Pop(h Interface) interface{} { - n := h.Len() - 1 - h.Swap(0, n) - down(h, 0, n) - return h.Pop() -} - -// Remove removes the element at index i from the heap. -// The complexity is O(log(n)) where n = h.Len(). -// -func Remove(h Interface, i int) interface{} { - n := h.Len() - 1 - if n != i { - h.Swap(i, n) - down(h, i, n) - up(h, i) - } - return h.Pop() -} - -func up(h Interface, j int) { - for { - i := (j - 1) / 2 // parent - if i == j || !h.Less(j, i) { - break - } - h.Swap(i, j) - j = i - } -} - -func down(h Interface, i, n int) { - for { - j1 := 2*i + 1 - if j1 >= n { - 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(j, i) { - break - } - h.Swap(i, j) - i = j - } -} |