heap

Documentation

Index

• func Example_intHeap()
• func TestPriorityQueue()
• type Heap
  • func NewIntHeap(items []int) *Heap
  • func (h *Heap) Items() []int
  • func (h *Heap) Pop() int
  • func (h *Heap) Push(data int)
• type IntHeap
  • func (h IntHeap) Len() int
  • func (h IntHeap) Less(i, j int) bool
  • func (h *IntHeap) Pop() interface{}
  • func (h *IntHeap) Push(x interface{})
  • func (h IntHeap) Swap(i, j int)
• type Item
• type PriorityQueue
  • func (pq PriorityQueue) Len() int
  • func (pq PriorityQueue) Less(i, j int) bool
  • func (pq *PriorityQueue) Pop() interface{}
  • func (pq *PriorityQueue) Push(x interface{})
  • func (pq PriorityQueue) Swap(i, j int)

Functions

func Example_intHeap

func Example_intHeap()

This example inserts several ints into an IntHeap, checks the minimum, and removes them in order of priority.

func TestPriorityQueue

func TestPriorityQueue()

Types

type Heap

type Heap struct {
	// contains filtered or unexported fields
}

实现大顶堆

func NewIntHeap

func NewIntHeap(items []int) *Heap

func (*Heap) Items

func (h *Heap) Items() []int

func (*Heap) Pop

func (h *Heap) Pop() int

func (*Heap) Push

func (h *Heap) Push(data int)

type IntHeap

type IntHeap []int

An IntHeap is a min-heap of ints.

func (IntHeap) Len

func (h IntHeap) Len() int

func (IntHeap) Less

func (h IntHeap) Less(i, j int) bool

由于是小顶堆, 所以前面的元素(堆顶)要比后面的小

func (*IntHeap) Pop

func (h *IntHeap) Pop() interface{}

Pop 弹出堆顶的元素, 还记得堆是如何删除元素的吗? 1. 取出堆顶的元素给你 2. 那现在堆顶的空位应该被如何补充 3. 把堆底的元素给他, 然后就是shift-down 我们这里Pop 就是给他最后一个元素, 后面的操作由heap包的pop帮我们完成(shift-donw)

func (*IntHeap) Push

func (h *IntHeap) Push(x interface{})

Push 往堆里面添加元素, 后面的调整由heap包帮我们完成(shift-up)

func (IntHeap) Swap

func (h IntHeap) Swap(i, j int)

交换2个元素的位置

type Item

type Item struct {
	// contains filtered or unexported fields
}

type PriorityQueue

type PriorityQueue []*Item

优先级队列需要实现heap的interface

func (PriorityQueue) Len

func (pq PriorityQueue) Len() int

绑定Len方法

func (PriorityQueue) Less

func (pq PriorityQueue) Less(i, j int) bool

绑定Less方法，这里用的是小于号，生成的是小根堆

func (*PriorityQueue) Pop

func (pq *PriorityQueue) Pop() interface{}

绑定put方法，将index置为-1是为了标识该数据已经出了优先级队列了

func (*PriorityQueue) Push

func (pq *PriorityQueue) Push(x interface{})

绑定push方法

func (PriorityQueue) Swap

func (pq PriorityQueue) Swap(i, j int)

绑定swap方法