```
Source File
heap.go
Belonging Package
container/heap
```

`// 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`

`// minimum-valued node in its subtree.`

`//`

`// The minimum element in the tree is the root, at index 0.`

`//`

`// 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_pq_test.go has the complete source.`

`package heap`

`import`

`// The Interface type describes the requirements`

`// for a type using the routines in this package.`

`// Any type that implements it 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 2*i+1 <= j <= 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 any) // add x as element Len()`

`Pop() any // remove and return element Len() - 1.`

`}`

`// Init establishes the heap invariants required by the other routines in this package.`

`// Init is idempotent with respect to the heap invariants`

`// and may be called whenever the heap invariants may have been invalidated.`

`// The complexity is O(n) where n = h.Len().`

`func ( Interface) {`

`// heapify`

`:= .Len()`

`for := /2 - 1; >= 0; -- {`

`down(, , )`

`}`

`}`

`// Push pushes the element x onto the heap.`

`// The complexity is O(log n) where n = h.Len().`

`func ( Interface, any) {`

`.Push()`

`up(, .Len()-1)`

`}`

`// Pop removes and returns the minimum element (according to Less) from the heap.`

`// The complexity is O(log n) where n = h.Len().`

`// Pop is equivalent to [Remove](h, 0).`

`func ( Interface) any {`

`:= .Len() - 1`

`.Swap(0, )`

`down(, 0, )`

`return .Pop()`

`}`

`// Remove removes and returns the element at index i from the heap.`

`// The complexity is O(log n) where n = h.Len().`

`func ( Interface, int) any {`

`:= .Len() - 1`

`if != {`

`.Swap(, )`

`if !down(, , ) {`

`up(, )`

`}`

`}`

`return .Pop()`

`}`

`// Fix re-establishes the heap ordering after the element at index i has changed its value.`

`// Changing the value of the element at index i and then calling Fix is equivalent to,`

`// but less expensive than, calling [Remove](h, i) followed by a Push of the new value.`

`// The complexity is O(log n) where n = h.Len().`

`func ( Interface, int) {`

`if !down(, , .Len()) {`

`up(, )`

`}`

`}`

`func up( Interface, int) {`

`for {`

`:= ( - 1) / 2 // parent`

`if == || !.Less(, ) {`

`break`

`}`

`.Swap(, )`

`=`

`}`

`}`

`func down( Interface, , int) bool {`

`:=`

`for {`

`:= 2* + 1`

`if >= || < 0 { // j1 < 0 after int overflow`

`break`

`}`

`:= // left child`

`if := + 1; < && .Less(, ) {`

`= // = 2*i + 2 // right child`

`}`

`if !.Less(, ) {`

`break`

`}`

`.Swap(, )`

`=`

`}`

`return >`

`}`

The pages are generated with Golds v0.6.9-preview. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds. |