example_intheap_test.go

     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 any) {
    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() any {
    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