heap

README

Go 堆排序

Install

go get github.com/golang-infrastructure/go-heap

Example

package main

import (
	"fmt"
	"github.com/golang-infrastructure/go-heap"
	"math/rand"
)

func main() {
	options := &heap.Options[int]{
		Comparator: heap.IntComparator(),
		// 支持N叉堆，默认是2叉堆
		Ary: 4,
	}

	// 非线程安全的堆，仅限于单个goroutine里使用
	//heap :=heap.New(heap.IntComparator())
	heap := heap.NewWithOptions(options)

	// 创建线程安全的堆
	//heap :=heap.NewSync(heap.IntComparator())
	//heap := heap.NewSyncWithOptions(options)
	for i := 0; i < 10; i++ {
		n := rand.Int() % 100
		heap.Push(n)
	}
	heapNumSlice := heap.PopToSlice()
	fmt.Println(heapNumSlice) // [10 16 20 21 37 48 49 51 51 58]
}

Documentation

Index

• Constants
• Variables
• type Comparator
  • func Float32Comparator() Comparator[float32]
  • func Float64Comparator() Comparator[float64]
  • func IntComparator() Comparator[int]
  • func StringComparator() Comparator[string]
  • func UintComparator() Comparator[uint]
• type Heap
  • func New[T any](comparator Comparator[T]) *Heap[T]
  • func NewWithOptions[T any](options *Options[T]) *Heap[T]
  • func (x *Heap[T]) Clear()
  • func (x *Heap[T]) ExportDotLanguage() string
  • func (x *Heap[T]) IsEmpty() bool
  • func (x *Heap[T]) IsNotEmpty() bool
  • func (x *Heap[T]) Peek() T
  • func (x *Heap[T]) PeekE() (T, error)
  • func (x *Heap[T]) Pop() T
  • func (x *Heap[T]) PopE() (T, error)
  • func (x *Heap[T]) PopEach(eachFunc func(v T) bool)
  • func (x *Heap[T]) PopToSlice() []T
  • func (x *Heap[T]) PopTopN(n int) []T
  • func (x *Heap[T]) Push(valueSlice ...T)
  • func (x *Heap[T]) Size() int
• type Interface
• type Options
• type SyncHeap
  • func NewSync[T any](comparator Comparator[T]) *SyncHeap[T]
  • func NewSyncWithOptions[T any](options *Options[T]) *SyncHeap[T]
  • func (x *SyncHeap[T]) Clear()
  • func (x *SyncHeap[T]) IsEmpty() bool
  • func (x *SyncHeap[T]) IsNotEmpty() bool
  • func (x *SyncHeap[T]) Peek() T
  • func (x *SyncHeap[T]) PeekE() (T, error)
  • func (x *SyncHeap[T]) Pop() T
  • func (x *SyncHeap[T]) PopE() (T, error)
  • func (x *SyncHeap[T]) PopEach(eachFunc func(v T) bool)
  • func (x *SyncHeap[T]) PopTopN(n int) []T
  • func (x *SyncHeap[T]) Push(valueSlice ...T)
  • func (x *SyncHeap[T]) Size() int

Constants

const DefaultAryHeap = 2

DefaultAryHeap 默认是2叉堆

Variables

var (
	// ErrHeapIsEmpty 堆是空的时候不能进行某些操作，会返回此错误
	ErrHeapIsEmpty = errors.New("heap is empty")
)

Types

type Comparator

type Comparator[T any] func(a T, b T) int

Comparator 用于比较堆中元素的大小

func Float32Comparator

func Float32Comparator() Comparator[float32]

func Float64Comparator

func Float64Comparator() Comparator[float64]

func IntComparator

func IntComparator() Comparator[int]

func StringComparator

func StringComparator() Comparator[string]

func UintComparator

func UintComparator() Comparator[uint]

type Heap

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

func New

func New[T any](comparator Comparator[T]) *Heap[T]

func NewWithOptions

func NewWithOptions[T any](options *Options[T]) *Heap[T]

func (*Heap[T]) Clear

func (x *Heap[T]) Clear()

Clear 把堆清空

func (*Heap[T]) ExportDotLanguage

func (x *Heap[T]) ExportDotLanguage() string

ExportDotLanguage 导出为dot language，拿出去画图以便可视化

func (*Heap[T]) IsEmpty

func (x *Heap[T]) IsEmpty() bool

func (*Heap[T]) IsNotEmpty

func (x *Heap[T]) IsNotEmpty() bool

IsNotEmpty 堆是否非空

func (*Heap[T]) Peek

func (x *Heap[T]) Peek() T

func (*Heap[T]) PeekE

func (x *Heap[T]) PeekE() (T, error)

PeekE 获取堆顶的元素，但并不弹出

func (*Heap[T]) Pop

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

func (*Heap[T]) PopE

func (x *Heap[T]) PopE() (T, error)

PopE 弹出堆顶的元素，如果堆是空的，则返回error

func (*Heap[T]) PopEach

func (x *Heap[T]) PopEach(eachFunc func(v T) bool)

func (*Heap[T]) PopToSlice

func (x *Heap[T]) PopToSlice() []T

func (*Heap[T]) PopTopN

func (x *Heap[T]) PopTopN(n int) []T

PopTopN n为正数时将前N个元素弹出，-1表示全部

func (*Heap[T]) Push

func (x *Heap[T]) Push(valueSlice ...T)

func (*Heap[T]) Size

func (x *Heap[T]) Size() int

type Interface

type Interface[T any] interface {
	Clear()

	Push(v ...T)

	PeekE() (T, error)
	Peek() T

	PopE() (T, error)
	Pop() T

	Size() int

	IsEmpty() bool
	IsNotEmpty() bool

	PopTopN(n int) []T
	PopEach(eachFunc func(v T) bool)
}

Interface 用于定义堆提供的API

type Options

type Options[T any] struct {

	// 必选项，比较器，用来决定堆中数据之前的相对大小
	Comparator Comparator[T]

	// 可选项，堆是几叉堆，默认是二叉堆
	Ary int

	// 可选项，可以从指定的数组初始化堆，不指定的话默认为空堆
	InitSlice []T
}

Options 堆排序的选项

type SyncHeap

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

SyncHeap 线程安全的堆

func NewSync

func NewSync[T any](comparator Comparator[T]) *SyncHeap[T]

func NewSyncWithOptions

func NewSyncWithOptions[T any](options *Options[T]) *SyncHeap[T]

func (*SyncHeap[T]) Clear

func (x *SyncHeap[T]) Clear()

func (*SyncHeap[T]) IsEmpty

func (x *SyncHeap[T]) IsEmpty() bool

func (*SyncHeap[T]) IsNotEmpty

func (x *SyncHeap[T]) IsNotEmpty() bool

func (*SyncHeap[T]) Peek

func (x *SyncHeap[T]) Peek() T

func (*SyncHeap[T]) PeekE

func (x *SyncHeap[T]) PeekE() (T, error)

func (*SyncHeap[T]) Pop

func (x *SyncHeap[T]) Pop() T

func (*SyncHeap[T]) PopE

func (x *SyncHeap[T]) PopE() (T, error)

func (*SyncHeap[T]) PopEach

func (x *SyncHeap[T]) PopEach(eachFunc func(v T) bool)

func (*SyncHeap[T]) PopTopN

func (x *SyncHeap[T]) PopTopN(n int) []T

func (*SyncHeap[T]) Push

func (x *SyncHeap[T]) Push(valueSlice ...T)

func (*SyncHeap[T]) Size

func (x *SyncHeap[T]) Size() int