heap

Documentation

Index

• type Heap
• type MaxHeap
  • func CreateMaxHeap(comparator func(thisValue interface{}, compareValue interface{}) int, ...) MaxHeap
  • func CreateMaxHeapDefault(comparator func(thisValue interface{}, compareValue interface{}) int) MaxHeap
  • func CreateMaxHeapFromSliceArray(comparator func(thisValue interface{}, compareValue interface{}) int, ...) MaxHeap
  • func (heap MaxHeap) Add(value interface{})
  • func (heap MaxHeap) ExtractTop() (interface{}, error)
  • func (heap MaxHeap) FindTop() (interface{}, error)
  • func (heap MaxHeap) GetSize() int
  • func (heap MaxHeap) IsEmpty() bool
  • func (heap MaxHeap) Replace(value interface{}) (interface{}, error)
• type MinHeap
  • func CreateMinHeap(comparator func(thisValue interface{}, compareValue interface{}) int, ...) MinHeap
  • func CreateMinHeapDefault(comparator func(thisValue interface{}, compareValue interface{}) int) MinHeap
  • func CreateMinHeapFromSliceArray(comparator func(thisValue interface{}, compareValue interface{}) int, ...) MinHeap
  • func (heap MinHeap) Add(value interface{})
  • func (heap MinHeap) ExtractTop() (interface{}, error)
  • func (heap MinHeap) FindTop() (interface{}, error)
  • func (heap MinHeap) GetSize() int
  • func (heap MinHeap) IsEmpty() bool
  • func (heap MinHeap) Replace(value interface{}) (interface{}, error)

Types

type Heap

type Heap interface {
	GetSize() int

	IsEmpty() bool

	Add(value interface{})

	FindTop() (interface{}, error)

	ExtractTop() (interface{}, error)

	Replace(value interface{}) (interface{}, error)
}

type MaxHeap

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

最大堆 堆是一棵完全二叉树

func CreateMaxHeap

func CreateMaxHeap(comparator func(thisValue interface{}, compareValue interface{}) int, capacity int) MaxHeap

创建一个指定容量的最大堆

func CreateMaxHeapDefault

func CreateMaxHeapDefault(comparator func(thisValue interface{}, compareValue interface{}) int) MaxHeap

创建一个默认容量的最大堆

func CreateMaxHeapFromSliceArray

func CreateMaxHeapFromSliceArray(comparator func(thisValue interface{}, compareValue interface{}) int, sourceSlice array.SliceArray) MaxHeap

O(n) 根据slice创建最大堆 使用heapify的方式将slice转换为最大堆

func (MaxHeap) Add

func (heap MaxHeap) Add(value interface{})

O(log(n)) 向完全二叉树的数组表示中,添加元素

func (MaxHeap) ExtractTop

func (heap MaxHeap) ExtractTop() (interface{}, error)

O(log(n)) 提取出最大的元素

func (MaxHeap) FindTop

func (heap MaxHeap) FindTop() (interface{}, error)

func (MaxHeap) GetSize

func (heap MaxHeap) GetSize() int

获取最大堆中元素的个数

func (MaxHeap) IsEmpty

func (heap MaxHeap) IsEmpty() bool

最大堆是否为空

func (MaxHeap) Replace

func (heap MaxHeap) Replace(value interface{}) (interface{}, error)

取出最大的一个元素后,放入一个新的元素

type MinHeap

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

func CreateMinHeap

func CreateMinHeap(comparator func(thisValue interface{}, compareValue interface{}) int, capacity int) MinHeap

创建一个指定容量的最小堆

func CreateMinHeapDefault

func CreateMinHeapDefault(comparator func(thisValue interface{}, compareValue interface{}) int) MinHeap

创建一个默认容量的最小堆

func CreateMinHeapFromSliceArray

func CreateMinHeapFromSliceArray(comparator func(thisValue interface{}, compareValue interface{}) int, sourceSlice array.SliceArray) MinHeap

O(n) 使用heapify的方式将slice转换为最小堆

func (MinHeap) Add

func (heap MinHeap) Add(value interface{})

func (MinHeap) ExtractTop

func (heap MinHeap) ExtractTop() (interface{}, error)

func (MinHeap) FindTop

func (heap MinHeap) FindTop() (interface{}, error)

func (MinHeap) GetSize

func (heap MinHeap) GetSize() int

func (MinHeap) IsEmpty

func (heap MinHeap) IsEmpty() bool

func (MinHeap) Replace

func (heap MinHeap) Replace(value interface{}) (interface{}, error)