example_intheap_test.go

Documentation: container/heap

		 1  // Copyright 2012 The Go Authors. All rights reserved.
		 2  // Use of this source code is governed by a BSD-style
		 3  // license that can be found in the LICENSE file.
		 4  
		 5  // This example demonstrates an integer heap built using the heap interface.
		 6  package heap_test
		 7  
		 8  import (
		 9  	"container/heap"
		10  	"fmt"
		11  )
		12  
		13  // An IntHeap is a min-heap of ints.
		14  type IntHeap []int
		15  
		16  func (h IntHeap) Len() int					 { return len(h) }
		17  func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
		18  func (h IntHeap) Swap(i, j int)			{ h[i], h[j] = h[j], h[i] }
		19  
		20  func (h *IntHeap) Push(x interface{}) {
		21  	// Push and Pop use pointer receivers because they modify the slice's length,
		22  	// not just its contents.
		23  	*h = append(*h, x.(int))
		24  }
		25  
		26  func (h *IntHeap) Pop() interface{} {
		27  	old := *h
		28  	n := len(old)
		29  	x := old[n-1]
		30  	*h = old[0 : n-1]
		31  	return x
		32  }
		33  
		34  // This example inserts several ints into an IntHeap, checks the minimum,
		35  // and removes them in order of priority.
		36  func Example_intHeap() {
		37  	h := &IntHeap{2, 1, 5}
		38  	heap.Init(h)
		39  	heap.Push(h, 3)
		40  	fmt.Printf("minimum: %d\n", (*h)[0])
		41  	for h.Len() > 0 {
		42  		fmt.Printf("%d ", heap.Pop(h))
		43  	}
		44  	// Output:
		45  	// minimum: 1
		46  	// 1 2 3 5
		47  }
		48
View as plain text