heaps

README

heap

heap是对标准库container/heap的简单封装。使堆结构更简单易用。

示例

普通小顶堆：

package main

import (
	"fmt"

	"github.com/eachain/heaps"
)

func main() {
	h := heaps.NewOrderedHeap[int]()
	h.Push(2)
	h.Push(1)
	h.Push(5)
	h.Push(3)
	fmt.Printf("minimum: %d\n", h.Top())
	for h.Len() > 0 {
		fmt.Printf("%d ", h.Pop())
	}
	// Output:
	// minimum: 1
	// 1 2 3 5
}

优先级队列：

package main

import (
	"fmt"

	"github.com/eachain/heaps"
)

func main() {
	pq := heaps.NewPriorityQueue[string](func(a, b int) bool {
		return a > b
	})
	pq.Push("banana", 3)
	pq.Push("apple", 2)
	pq.Push("pear", 4)
	pq.Push("orange", 1)
	pq.Update("orange", 5)

	for pq.Len() > 0 {
		item, priority := pq.Pop()
		fmt.Printf("%.2d:%s ", priority, item)
	}
}

Documentation

Index

• type Heap
  • func NewHeap[T any](less LessFunc[T]) *Heap[T]
  • func NewOrderedHeap[T cmp.Ordered]() *Heap[T]
  • func (h *Heap[T]) Count(v T) int
  • func (h *Heap[T]) Len() int
  • func (h *Heap[T]) Pop() T
  • func (h *Heap[T]) Push(v T)
  • func (h *Heap[T]) Remove(v T, n int) int
  • func (h *Heap[T]) Top() T
• type LessFunc
• type PriorityQueue
  • func NewOrderedPriorityQueue[E comparable, P cmp.Ordered]() *PriorityQueue[E, P]
  • func NewPriorityQueue[E comparable, P any](less LessFunc[P]) *PriorityQueue[E, P]
  • func (pq *PriorityQueue[E, P]) Len() int
  • func (pq *PriorityQueue[E, P]) Pop() (E, P)
  • func (pq *PriorityQueue[E, P]) PriorityOf(item E) (priority P, ok bool)
  • func (pq *PriorityQueue[E, P]) Push(item E, priority P)
  • func (pq *PriorityQueue[E, P]) Remove(item E) (priority P, ok bool)
  • func (pq *PriorityQueue[E, P]) Top() (E, P)
  • func (pq *PriorityQueue[E, P]) Update(item E, priority P) bool

Types

type Heap

type Heap[T any] struct {
	// contains filtered or unexported fields
}

func NewHeap

func NewHeap[T any](less LessFunc[T]) *Heap[T]

func NewOrderedHeap

func NewOrderedHeap[T cmp.Ordered]() *Heap[T]

func (*Heap[T]) Count

func (h *Heap[T]) Count(v T) int

Count returns the count of elements equal v.

func (*Heap[T]) Len

func (h *Heap[T]) Len() int

func (*Heap[T]) Pop

func (h *Heap[T]) Pop() T

func (*Heap[T]) Push

func (h *Heap[T]) Push(v T)

func (*Heap[T]) Remove

func (h *Heap[T]) Remove(v T, n int) int

Count returns the count of elements equal v removed. The param n points how many elements to remove, -1 named all.

func (*Heap[T]) Top

func (h *Heap[T]) Top() T

type LessFunc

type LessFunc[T any] func(a, b T) bool

LessFunc compare a and b, it should returns true on a < b, and false on a >= b.

type PriorityQueue

type PriorityQueue[E comparable, P any] struct {
	// contains filtered or unexported fields
}

func NewOrderedPriorityQueue

func NewOrderedPriorityQueue[E comparable, P cmp.Ordered]() *PriorityQueue[E, P]

func NewPriorityQueue

func NewPriorityQueue[E comparable, P any](less LessFunc[P]) *PriorityQueue[E, P]

func (*PriorityQueue[E, P]) Len

func (pq *PriorityQueue[E, P]) Len() int

func (*PriorityQueue[E, P]) Pop

func (pq *PriorityQueue[E, P]) Pop() (E, P)

func (*PriorityQueue[E, P]) PriorityOf

func (pq *PriorityQueue[E, P]) PriorityOf(item E) (priority P, ok bool)

func (*PriorityQueue[E, P]) Push

func (pq *PriorityQueue[E, P]) Push(item E, priority P)

func (*PriorityQueue[E, P]) Remove

func (pq *PriorityQueue[E, P]) Remove(item E) (priority P, ok bool)

func (*PriorityQueue[E, P]) Top

func (pq *PriorityQueue[E, P]) Top() (E, P)

func (*PriorityQueue[E, P]) Update

func (pq *PriorityQueue[E, P]) Update(item E, priority P) bool