Documentation
¶
Index ¶
- type ComparerFunc
- type Heap
- func (h *Heap[V]) BinarySearch(target V, compareFn func(a V, b V) int) func(yield func(int, bool) bool)
- func (h *Heap[V]) DeleteElement(idx int)
- func (h *Heap[V]) Fix(i int)
- func (h *Heap[V]) GetByIndex(idx int) V
- func (h *Heap[V]) Init()
- func (h *Heap[V]) Iter() func(yield func(int, V) bool)
- func (h *Heap[V]) Len() int
- func (h *Heap[V]) Less(i, j int) bool
- func (h *Heap[V]) Pop() any
- func (h *Heap[V]) PopElement() (V, bool)
- func (h *Heap[V]) Push(v any)
- func (h *Heap[V]) PushElement(v V)
- func (h *Heap[V]) SetByIndex(idx int, v V)
- func (h *Heap[V]) Sort()
- func (h *Heap[V]) SortByOtherFn(sortFn ComparerFunc[V])
- func (h *Heap[V]) Swap(i, j int)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ComparerFunc ¶
type Heap ¶
type Heap[V any] struct { // contains filtered or unexported fields }
Example ¶
package main
import (
"fmt"
"github.com/Genry72/helper/priorityquery"
"strings"
)
type Item struct {
value string
priority int
}
func main() {
// Cписок продуктов и их приоритеты
items := map[string]int{
"banana": 3, "apple": 2, "pear": 4,
}
h := priorityquery.NewHeap[Item](len(items), func(a, b Item) bool {
return a.priority > b.priority
})
for name, priority := range items {
h.PushElement(Item{
value: name,
priority: priority,
})
}
h.PushElement(Item{
value: "orange",
priority: 1,
})
h2 := priorityquery.NewHeap[Item](h.Len(), func(a, b Item) bool {
return a.priority > b.priority
})
// Вычитываем все элементы из кучи и записываем в новую
for h.Len() > 0 {
item, _ := h.PopElement()
h2.PushElement(item)
fmt.Printf("%s:%.2d\n", item.value, item.priority)
}
fmt.Println("len(h) = ", h.Len())
// Так как куча отсортирована по значению приоритета, сортируем по имени для выполнения бинарного поиска
h2.SortByOtherFn(func(a, b Item) bool {
return a.value < b.value
})
var orangeIdx int
for idx, ok := range h2.BinarySearch(Item{value: "orange"}, func(a Item, b Item) int {
return strings.Compare(a.value, b.value)
}) {
if !ok {
panic("orange not fount") // !!! не использовать в проде)
}
orangeIdx = idx
}
h2.SetByIndex(orangeIdx, Item{
value: "orange",
priority: 100,
})
// Применяем исходную сортировку
h2.Sort()
// Проход по всем элементам, оставляя в куче. Здесь сортировка на гарантируется
for _, v := range h2.Iter() {
fmt.Printf("%s:%.2d\n", v.value, v.priority)
}
}
Output: pear:04 banana:03 apple:02 orange:01 len(h) = 0 orange:100 pear:04 banana:03 apple:02
func NewFromSlice ¶
func NewFromSlice[V any](sl []V, less ComparerFunc[V]) *Heap[V]
Example ¶
package main
import (
"fmt"
"github.com/Genry72/helper/priorityquery"
)
type Items struct {
value string
priority int
}
func main() {
// Cписок продуктов и их приоритеты
items := []*Items{
{
value: "banana",
priority: 3,
},
{
value: "apple",
priority: 2,
},
{
value: "pear",
priority: 4,
},
}
h := priorityquery.NewFromSlice(items, func(a, b *Items) bool {
return a.priority > b.priority
})
h.PushElement(&Items{
value: "orange",
priority: 1,
})
// Вычитываем все элементы из кучи
for h.Len() > 0 {
item, _ := h.PopElement()
fmt.Printf("%s:%.2d\n", item.value, item.priority)
}
}
Output: pear:04 banana:03 apple:02 orange:01
func NewHeap ¶
func NewHeap[V any](count int, less ComparerFunc[V]) *Heap[V]
Example ¶
package main
import (
"fmt"
"github.com/Genry72/helper/priorityquery"
)
func main() {
// Cписок продуктов и их приоритеты
items := []int{}
h := priorityquery.NewFromSlice[int](items, func(a, b int) bool {
return a > b
})
for i := 0; i < 10; i++ {
h.PushElement(i)
}
for i, v := range h.Iter() {
if v > 5 {
h.DeleteElement(i)
}
}
// Вычитываем все элементы из кучи
for h.Len() > 0 {
item, _ := h.PopElement()
fmt.Printf("%d\n", item)
}
}
Output: 5 4 3 2 1 0
func (*Heap[V]) BinarySearch ¶
func (h *Heap[V]) BinarySearch(target V, compareFn func(a V, b V) int) func(yield func(int, bool) bool)
BinarySearch Убедитесь что куча отсортирована в порядке возрастания (либо измените приведенный пример ниже), по нужному ключу (вызовите метод Sort) иначе воспользуйтесь линейным поиском используя Iter, либо отсортируйте массив по другому принципу, используя метод SortByOtherFn
return a.priority - b.priority Для возрастающей последовательности int return strings.Compare(a.value, b.value) Для возрастающей последовательности строк Общий подход для возрастающей последовательности
if a == b {
return 0
}
if a < b {
return -1
}
return 1
func (*Heap[V]) DeleteElement ¶
DeleteElement Удаление элемента по индексу
func (*Heap[V]) GetByIndex ¶
func (*Heap[V]) Init ¶
func (h *Heap[V]) Init()
Init Восстанавливает кучу, если она была изменена. Не делает ничего, если куча уже отсортирована.
func (*Heap[V]) Iter ¶
Iter Итерация по всем элементам. Сортировка не гарантируется. Вызоаите дополнительно метод Sort либо используйте PopElement
func (*Heap[V]) Pop ¶
Pop Реализация интерфейса heap.Interface. Возвращает первый элемент из кучи. И удаляет его. Не восстанавливает кучу
func (*Heap[V]) PopElement ¶
PopElement Возвращает первый элемент из кучи. И удаляет его. Восстановление свойства кучи
func (*Heap[V]) PushElement ¶
func (h *Heap[V]) PushElement(v V)
PushElement Добавление элемента, восстановление кучи
func (*Heap[V]) SetByIndex ¶
SetByIndex Устанавливает новое значение
func (*Heap[V]) SortByOtherFn ¶
func (h *Heap[V]) SortByOtherFn(sortFn ComparerFunc[V])
SortByOtherFn Сортировка массива по отличной, переданной сортировки при инициализации кучи Когда данная сортировка будет не нужна, нужно вызвать метод Init, для восстановления состояния кучи
Source Files