Package heap

import "container/heap"
Overview
Index
Examples

Overview ▾

包堆为实现了heap.Interface的任何类型提供堆操作. 堆是一棵树,其属性为每个节点是其子树中的最小值节点.

树中的最小元素是根,索引为0.

堆是实现优先级队列的常用方法. 要构建优先级队列,请以(负)优先级实现Heap接口,作为Less方法的顺序,因此Push添加项,而Pop删除队列中优先级最高的项. 示例包括这样的实现; 文件example_pq_test.go包含完整的源代码.

示例(IntHeap)

本示例将多个int插入IntHeap中,检查最小值,然后按优先级顺序将其删除.

minimum: 1
1 2 3 5

示例(PriorityQueue)

本示例创建一个包含某些项目的PriorityQueue,添加和操作一个项目,然后按优先级顺序删除这些项目.

05:orange 04:pear 03:banana 02:apple

func Fix 1.2

func Fix(h Interface, i int)

在索引i的元素更改其值之后,Fix会重新建立堆顺序. 更改索引i处元素的值,然后调用Fix等效于,但比调用Remove(h,i)紧随其后的是推入新值,但其开销要小. 复杂度为O(log n),其中n = h.Len().

func Init

func Init(h Interface)

Init建立此程序包中其他例程所需的堆不变式. 关于堆不变式,Init是幂等的,只要使堆不变式无效,就可以调用它. 复杂度为O(n),其中n = h.Len().

func Pop

func Pop(h Interface) interface{}

Pop从堆中删除并返回最小元素(根据Less). 复杂度为O(log n),其中n = h.Len(). Pop等效于Remove(h,0).

func Push

func Push(h Interface, x interface{})

Push将元素x推入堆. 复杂度为O(log n),其中n = h.Len().

func Remove

func Remove(h Interface, i int) interface{}

Remove从堆中删除并返回索引i处的元素. 复杂度为O(log n),其中n = h.Len().

type Interface

接口类型使用此包中的例程描述对类型的要求. 任何实现它的类型都可以用作具有以下不变量的最小堆(在调用Init或数据为空或已排序之后建立):

!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()

请注意,此接口中的Push和Pop是供程序包堆的实现调用的. 要从堆中添加和删除内容,请使用heap.Push和heap.Pop.

type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

by  ICOPY.SITE