?
This document uses PHP Chinese website manual Release
import "container/heap"
概述
索引
例子
概述
Heap 包為任何實(shí)現(xiàn) heap.Interface 的類型提供堆操作。堆是具有屬性的樹，每個(gè)節(jié)點(diǎn)是其子樹中的最小值節(jié)點(diǎn)。
樹中的最小元素是索引為0的根。
堆是實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的常用方式。要構(gòu)建一個(gè)優(yōu)先級(jí)隊(duì)列，請(qǐng)將具有（負(fù)）優(yōu)先級(jí)的 Heap 接口作為 Less 方法的排序來(lái)執(zhí)行，因此推送會(huì)添加項(xiàng)目，而Pop 將從隊(duì)列中移除最高優(yōu)先級(jí)的項(xiàng)目。這些例子包括這樣的實(shí)現(xiàn)；文件example_pq_test.go 具有完整的源代碼。
示例 (IntHeap)
本示例將幾個(gè) int 插入到 IntHeap 中，檢查最小值，并按優(yōu)先級(jí)順序刪除它們。
// 本示例演示了使用堆接口構(gòu)建的整數(shù)堆。package mainimport ("container/heap""fmt")// IntHeap是一個(gè)整數(shù)的整數(shù)。type IntHeap []intfunc (h IntHeap) Len() int { return len(h) }func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }func (h *IntHeap) Push(x interface{}) {// Push和Pop使用指針接收器，因?yàn)樗鼈冃薷那衅拈L(zhǎng)度，// 不僅僅是其內(nèi)容。*h = append(*h, x.(int))}func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]*h = old[0 : n-1]return x}// 本示例將幾個(gè)int插入到IntHeap中，檢查最小值，// 并按優(yōu)先順序刪除它們。func main() {
h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
fmt.Printf("minimum: %d\n", (*h)[0])for h.Len() > 0 {
fmt.Printf("%d ", heap.Pop(h))}}示例 (PriorityQueue)
本示例使用某些項(xiàng)目創(chuàng)建 PriorityQueue，添加并操作項(xiàng)目，然后按優(yōu)先級(jí)順序刪除項(xiàng)目。
// 此示例演示使用堆接口構(gòu)建的優(yōu)先級(jí)隊(duì)列。package mainimport ("container/heap""fmt")// item是我們?cè)趦?yōu)先隊(duì)列中管理的item。type Item struct {
value string // item的值；任意取值。
priority int // 隊(duì)列中項(xiàng)目的優(yōu)先級(jí)。// 該索引是更新所需的，由heap.Interface方法維護(hù)。
index int // 堆中項(xiàng)目的索引。}// PriorityQueue實(shí)現(xiàn)堆。接口并保存項(xiàng)目。type PriorityQueue []*Itemfunc (pq PriorityQueue) Len() int { return len(pq) }func (pq PriorityQueue) Less(i, j int) bool {// 我們希望Pop給我們最高的優(yōu)先權(quán)，而不是最低的優(yōu)先權(quán)，所以我們使用的比這里更大。return pq[i].priority > pq[j].priority}func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j}func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
item := x.(*Item)
item.index = n*pq = append(*pq, item)}func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
item.index = -1 // for safety*pq = old[0 : n-1]return item}// 更新修改隊(duì)列中某個(gè)項(xiàng)目的優(yōu)先級(jí)和值。func (pq *PriorityQueue) update(item *Item, value string, priority int) {
item.value = value
item.priority = priority
heap.Fix(pq, item.index)}// 本示例使用某些項(xiàng)目創(chuàng)建PriorityQueue，添加和操作項(xiàng)目，// 然后按優(yōu)先順序刪除這些項(xiàng)目。func main() {// 一些項(xiàng)目和它們的優(yōu)先級(jí)。
items := map[string]int{"banana": 3, "apple": 2, "pear": 4,}// 創(chuàng)建一個(gè)優(yōu)先級(jí)隊(duì)列，將其中的項(xiàng)目，和// 建立優(yōu)先隊(duì)列（堆）不變量。
pq := make(PriorityQueue, len(items))
i := 0for value, priority := range items {
pq[i] = &Item{
value: value,
priority: priority,
index: i,}
i++}
heap.Init(&pq)// 插入一個(gè)新項(xiàng)目，然后修改其優(yōu)先級(jí)。
item := &Item{
value: "orange",
priority: 1,}
heap.Push(&pq, item)
pq.update(item, item.value, 5)// 取出項(xiàng)目；以優(yōu)先順序遞減排列。for pq.Len() > 0 {
item := heap.Pop(&pq).(*Item)
fmt.Printf("%.2d:%s ", item.priority, item.value)}}索引
func Fix(h Interface, i int)
func Init(h Interface)
func Pop(h Interface) interface{}
func Push(h Interface, x interface{})
func Remove(h Interface, i int) interface{}
type Interface
示例
Package (IntHeap) Package (PriorityQueue)
包文件
heap.go
func Fix
func Fix(h Interface, i int)
Fix 在索引 i 處的元素已更改其值后重新建立堆排序。更改索引為 i 的元素的值，然后調(diào)用 Fix 相當(dāng)于調(diào)用 Remove(h, i)，然后再調(diào)用新值的代價(jià)。復(fù)雜度為 O(log(n))，其中 n = h.Len()。
func Init
func Init(h Interface)
必須在使用任何堆操作之前初始化堆。Init 對(duì)于堆不變式是冪等的，當(dāng)堆不變量可能已經(jīng)失效時(shí)可以調(diào)用Init。它的復(fù)雜性是 O(n)，其中n = h.Len()。
func Pop
func Pop(h Interface) interface{}Pop 從堆中刪除最小元素（根據(jù)Less）并返回。復(fù)雜度為 O(log(n))，其中 n = h.Len()。它相當(dāng)于 Remove(h, 0)。
func Push
func Push(h Interface, x interface{})推動(dòng)元素 x 到堆上。復(fù)雜度為 O(log(n))，其中 n = h.Len()。
func Remove
func Remove(h Interface, i int) interface{}從堆中刪除索引 i 處的元素。復(fù)雜度為 O(log(n))，其中 n = h.Len()。
type Interface
任何實(shí)現(xiàn)堆的類型 .Interface 可用作具有以下不變式的最小堆（在調(diào)用 Init 之后或數(shù)據(jù)為空或排序后建立）：
!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()
請(qǐng)注意，此接口中的 Push 和 Pop 用于調(diào)用包堆的實(shí)現(xiàn)。要從堆中添加和刪除東西，請(qǐng)使用 heap.Push 和 heap.Pop。
type Interface interface {
sort.Interface Push(x interface{}) // 將x添加為元素Len() Pop() interface{} // 刪除并返回元素Len()-1.}