Слайсы в Go

// Разные способы создания слайсов
empty := []int{}           // пустой слайс
withValues := []int{1, 2, 3, 4, 5}  // с начальными значениями
withMake := make([]int, 5)          // длиной 5, заполненный нулями
withCapacity := make([]int, 3, 10)  // длиной 3 и ёмкостью 10

Базовый массив: [0][1][2][3][4][5][6][7][8][9]
                  ↑       ↑           ↑
                  |       |           |
              указатель   |           |
                     длина (3)        |
                                  ёмкость (7)

type slice struct {
    array unsafe.Pointer  // указатель на базовый массив
    len   int             // количество доступных элементов
    cap   int             // максимальное количество элементов без перераспределения
}

newcap := old.cap
doublecap := newcap + newcap
if newcap < 1024 {
    newcap = doublecap
} else {
    for newcap < cap {
        newcap += newcap / 4
    }
}

func createSlice() []int {
    s := make([]int, 3)
    return s
}

func doSomething() {
    s := make([]int, 3)
    for i := 0; i < 3; i++ {
        s[i] = i
    }
    // используем s, но не возвращаем
}

go build -gcflags="-m" yourprogram.go

// Потенциально опасный код
s := []int{1, 2, 3}
go func() {
    time.Sleep(time.Second)
    fmt.Println(s[0]) // к этому моменту s может измениться
}()
s[0] = 999 // изменение влияет на горутину

// Неоптимально
for _, item := range items {
    var results []Result
    // каждая итерация создает новый слайс
    for _, x := range item.Data {
        results = append(results, process(x))
    }
    // обработка results
}
 
// Эффективнее
for _, item := range items {
    results := make([]Result, 0, len(item.Data))
    for _, x := range item.Data {
        results = append(results, process(x))
    }
    // обработка results
}

results := make([]Result, 0, 100)
for _, item := range items {
    results = results[:0] // очистка без перевыделения
    for _, x := range item.Data {
        results = append(results, process(x))
    }
    // обработка results
}

// Очистка слайса без изменения ёмкости
s = s[:0]

original := []int{0, 1, 2, 3, 4, 5}
sub := original[2:4] // [2, 3]

original := []int{0, 1, 2, 3, 4, 5}
sub := original[2:4]     // [2, 3]
sub[0] = 999             // изменяем sub
fmt.Println(original)    // [0, 1, 999, 3, 4, 5] - оригинал тоже изменился!

data, _ := ioutil.ReadFile("huge.file") // 1GB данных
line := data[0:100]                     // маленький подслайс
// data больше не нужен, но...

line := make([]byte, 100)
copy(line, data[0:100])
// теперь data может быть собран GC

var nilSlice []int         // nil-слайс (nil, 0, 0)
emptySlice := []int{}      // пустой слайс (указатель на пустой массив, 0, 0)
zeroLenSlice := make([]int, 0) // то же, что emptySlice

fmt.Println(nilSlice == nil)        // true
fmt.Println(emptySlice == nil)      // false
fmt.Println(zeroLenSlice == nil)    // false

func append(s []T, elements ...T) []T {
    // Проверяем, достаточно ли ёмкости
    if len(s)+len(elements) <= cap(s) {
        // Достаточно места, просто копируем новые элементы
        s = s[:len(s)+len(elements)]
        copy(s[len(s)-len(elements):], elements)
        return s
    }
    
    // Недостаточно места, создаём новый слайс с увеличенной ёмкостью
    newCap := growCap(cap(s), len(s)+len(elements))
    newSlice := make([]T, len(s)+len(elements), newCap)
    copy(newSlice, s)
    copy(newSlice[len(s):], elements)
    return newSlice
}

// Правильно
s = append(s, element)
 
// Неправильно - если произойдёт перераспределение,
// s продолжит указывать на старый массив
append(s, element)

copy(dst []T, src []T) int // возвращает количество скопированных элементов

a := []int{1, 2, 3}
b := make([]int, 2)
n := copy(b, a)     // n = 2, b = [1, 2]
c := make([]int, 5)
m := copy(c, a)     // m = 3, c = [1, 2, 3, 0, 0]

// Удаление элемента с индексом i
copy(s[i:], s[i+1:])
s = s[:len(s)-1]
 
// Вставка элемента на позицию i
s = append(s, 0)           // Добавляем место (можно предварительно проверить cap)
copy(s[i+1:], s[i:])       // Сдвигаем элементы
s[i] = newElement          // Вставляем новый элемент

// Пытаемся "оптимизировать", избегая повторных вызовов len()
l := len(s)
for i := 0; i < l; i++ {
    // работаем с s[i]
}

for i := 0; i < len(s); i++ {
    // работаем с s[i]
}

// Поиск в отсортированном слайсе
index, found := slices.BinarySearch(sortedSlice, targetValue)
 
// Поиск с пользовательской функцией сравнения
index, found := slices.BinarySearchFunc(sortedSlice, targetValue, compareFunc)

nums := []int{1, 2, 3, 4, 5, 6}
 
// Поиск существующего элемента
idx, found := slices.BinarySearch(nums, 4)
// idx = 3, found = true
 
// Поиск отсутствующего элемента
idx, found = slices.BinarySearch(nums, 7)
// idx = 6, found = false (т.е. вставить нужно в конец)

func compare(a, b int) int {
    return a - b
}
 
idx, found := slices.BinarySearchFunc(nums, 5, compare)

// Проверка равенства слайсов
equal := slices.Equal(slice1, slice2)
 
// Сравнение с пользовательской функцией
equal := slices.EqualFunc(slice1, slice2, compareFunc)
 
// Определение порядка (меньше, равно или больше)
result := slices.Compare(slice1, slice2)

list1 := []int{1, 2, 3, 4, 5}
list2 := []int{1, 2, 6, 4, 5}
list3 := []int{1, 2, 3, 4, 5}
 
// list1 == list3, но list1 < list2 (так как 3 < 6 на третьей позиции)
fmt.Println(slices.Compare(list1, list2)) // -1
fmt.Println(slices.Equal(list1, list3))   // true

s := make([]int, 3, 10)
fmt.Println(len(s), cap(s)) // 3 10
 
s = slices.Clip(s)
fmt.Println(len(s), cap(s)) // 3 3

original := []int{1, 2, 3, 4, 5}
copy := slices.Clone(original)
copy[0] = 99
// original остаётся [1, 2, 3, 4, 5]
// copy становится [99, 2, 3, 4, 5]

nums := []int{1, 1, 2, 2, 3, 3, 3, 4, 5, 5}
nums = slices.Compact(nums)
fmt.Println(nums) // [1, 2, 3, 4, 5]

type Person struct {
    ID   int
    Name string
}
 
// Считаем людей с одинаковым ID дубликатами
compacted := slices.CompactFunc(people, func(a, b Person) bool {
    return a.ID == b.ID
})

found := slices.Contains([]int{1, 2, 3, 4}, 3) // true
found := slices.Contains([]string{"a", "b", "c"}, "z") // false

func Contains[E comparable](s []E, v E) bool {
    for _, vs := range s {
        if v == vs {
            return true
        }
    }
    return false
}

// Проверяем, есть ли строка, начинающаяся с "prefix"
found := slices.ContainsFunc(strings, func(s string) bool {
    return strings.HasPrefix(s, "prefix")
})

// Удалить элементы с индексами от i до j (не включая j)
slice = slices.Delete(slice, i, j)
 
// Пример: удаление второго элемента
nums := []int{1, 2, 3, 4, 5}
nums = slices.Delete(nums, 1, 2)
fmt.Println(nums) // [1, 3, 4, 5]

// Сортировка слайса по возрастанию
slices.Sort(nums)
 
// Сортировка с пользовательской функцией сравнения
slices.SortFunc(persons, func(a, b Person) int {
    return a.Age - b.Age
})
 
// Проверка, отсортирован ли слайс
sorted := slices.IsSorted(nums)

// Фильтрация элементов без выделения новой памяти
j := 0
for i := 0; i < len(s); i++ {
    if keepElement(s[i]) {
        s[j] = s[i]
        j++
    }
}
s = s[:j]

// Базовый способ конкатенации
result := append(slice1, slice2...)

// Эффективная конкатенация
totalLen := len(slice1) + len(slice2)
result := make([]int, 0, totalLen)
result = append(result, slice1...)
result = append(result, slice2...)

allSlices := [][]int{slice1, slice2, slice3, slice4}
result := slices.Concat(allSlices...)

// До Go 1.18
mapped := make([]string, len(numbers))
for i, n := range numbers {
    mapped[i] = strconv.Itoa(n)
}
 
// С дженериками (Go 1.18+)
func Map[T, U any](s []T, f func(T) U) []U {
    result := make([]U, len(s))
    for i, v := range s {
        result[i] = f(v)
    }
    return result
}
 
// Использование
strings := Map(numbers, strconv.Itoa)

// Традиционный подход
filtered := make([]int, 0, len(numbers))
for _, n := range numbers {
    if n%2 == 0 { // Только чётные числа
        filtered = append(filtered, n)
    }
}
 
// С дженериками (Go 1.18+)
func Filter[T any](s []T, f func(T) bool) []T {
    result := make([]T, 0, len(s))
    for _, v := range s {
        if f(v) {
            result = append(result, v)
        }
    }
    return result
}
 
// Использование
evenNumbers := Filter(numbers, func(n int) bool { return n%2 == 0 })

// Сумма элементов слайса
sum := 0
for _, n := range numbers {
    sum += n
}
 
// С дженериками (Go 1.18+)
func Reduce[T, U any](s []T, initial U, f func(U, T) U) U {
    result := initial
    for _, v := range s {
        result = f(result, v)
    }
    return result
}
 
// Использование
sum := Reduce(numbers, 0, func(a, b int) int { return a + b })

// Создание двумерной матрицы 3x3
matrix := make([][]int, 3)
for i := range matrix {
    matrix[i] = make([]int, 3)
}
 
// Заполнение
for i := range matrix {
    for j := range matrix[i] {
        matrix[i][j] = i*3 + j + 1
    }
}

// Функция, возвращающая "неизменяемый" слайс
func ImmutableSlice(data []int) func(int) int {
    // Создаём копию для безопасности
    dataCopy := make([]int, len(data))
    copy(dataCopy, data)
    
    // Возвращаем замыкание для доступа к данным
    return func(index int) int {
        if index < 0 || index >= len(dataCopy) {
            panic("index out of range")
        }
        return dataCopy[index]
    }
}
 
// Использование
data := []int{1, 2, 3}
immutable := ImmutableSlice(data)
value := immutable(1) // 2

// Потенциальная утечка памяти
data := make([]byte, 1000000)
// ... работаем с данными ...
data = data[900000:] // Только последние 100k байт

// Предотвращение утечки
tail := make([]byte, len(data)-900000)
copy(tail, data[900000:])
data = tail

func GetEmptyData() []int {
    return []int{} // Возвращает пустой слайс (не nil)
}
 
func GetNilData() []int {
    return nil // Возвращает nil-слайс
}

// ОПАСНО: использовать только в исключительных случаях!
func unsafeCast(ints []int) []int64 {
    // Это ломает систему типов Go, используйте с крайней осторожностью
    header := (*reflect.SliceHeader)(unsafe.Pointer(&ints))
    header64 := reflect.SliceHeader{
        Data: header.Data,
        Len:  header.Len,
        Cap:  header.Cap,
    }
    return *(*[]int64)(unsafe.Pointer(&header64))
}

list := []int{1, 2, 3, 4, 5, 6}
hasZero := slices.Contains(list, 0)  // false
hasFour := slices.Contains(list, 4)  // true

type User struct {
    ID   int
    Name string
}
 
users := []User{{1, "Алиса"}, {2, "Боб"}, {3, "Карл"}}
 
// Ищем пользователя с ID = 2
found := slices.ContainsFunc(users, func(u User) bool {
    return u.ID == 2
})

func contains(s []string, e string) bool {
    for _, a := range s {
        if a == e {
            return true
        }
    }
    return false
}

// Удаление элемента с индексом i
func remove(s []int, i int) []int {
    // Копируем последний элемент на место удаляемого
    s[i] = s[len(s)-1]
    // Возвращаем слайс без последнего элемента
    return s[:len(s)-1]
}

// Удаление с сохранением порядка
func removeOrdered(s []int, i int) []int {
    copy(s[i:], s[i+1:])
    return s[:len(s)-1]
}

list := []int{1, 2, 3, 4, 5, 6}
list = slices.Delete(list, 1, 2)  // Удаляет элемент с индексом 1
fmt.Println(list)  // [1, 3, 4, 5, 6]

original := []int{1, 2, 3}
shallow := original
shallow[0] = 999
fmt.Println(original[0])  // 999 - оригинал тоже изменился!

original := []int{1, 2, 3}
deep := make([]int, len(original))
copy(deep, original)
deep[0] = 999
fmt.Println(original[0])  // 1 - оригинал не изменился

original := []int{1, 2, 3}
deep := slices.Clone(original)
deep[0] = 999
fmt.Println(original[0])  // 1 - оригинал не изменился

s := []int{1, 2, 3}
fmt.Println(s[5])  // panic: index out of range

func getSafely(s []int, i int) (int, error) {
    if i < 0 || i >= len(s) {
        return 0, fmt.Errorf("индекс %d вне диапазона [0:%d]", i, len(s))
    }
    return s[i], nil
}

s1 := []int{1, 2, 3}
s2 := []int{1, 2, 3}
fmt.Println(s1 == s2)  // ошибка компиляции

func equal(a, b []int) bool {
    if len(a) != len(b) {
        return false
    }
    for i, v := range a {
        if v != b[i] {
            return false
        }
    }
    return true
}

s1 := []int{1, 2, 3}
s2 := []int{1, 2, 3}
s3 := []int{1, 2, 4}
 
fmt.Println(slices.Equal(s1, s2))  // true
fmt.Println(slices.Equal(s1, s3))  // false

type Person struct {
    ID   int
    Name string
}
 
// Считаем персон равными, если у них одинаковый ID
equal := slices.EqualFunc(people1, people2, func(a, b Person) bool {
    return a.ID == b.ID
})

result := slices.Compare(s1, s2)
// -1: s1 < s2
//  0: s1 == s2
//  1: s1 > s2

// Опасный код!
s := []int{1, 2, 3}
go func() {
    s[0] = 999  // Запись без синхронизации
}()
fmt.Println(s[0])  // Чтение без синхронизации

var mu sync.Mutex
s := []int{1, 2, 3}
 
go func() {
    mu.Lock()
    s[0] = 999
    mu.Unlock()
}()
 
mu.Lock()
fmt.Println(s[0])
mu.Unlock()

type SlicePool struct {
pool sync.Pool
}
 
func NewSlicePool() *SlicePool {
return &SlicePool{
    pool: sync.Pool{
        New: func() interface{} {
            slice := make([]byte, 0, 4096) // начальная ёмкость
            return &slice
        },
    },
}
}
 
func (p *SlicePool) Get() *[]byte {
return p.pool.Get().(*[]byte)
}
 
func (p *SlicePool) Put(s *[]byte) {
*s = (*s)[:0] // очищаем содержимое, сохраняя ёмкость
p.pool.Put(s)
}

func processLargeFile(filename string) error {
file, err := os.Open(filename)
if err != nil {
    return err
}
defer file.Close()
 
buffer := make([]byte, 32*1024) // 32KB буфер
for {
    n, err := file.Read(buffer)
    if err == io.EOF {
        break
    }
    if err != nil {
        return err
    }
    
    // Обрабатываем данные из buffer[:n]
    processChunk(buffer[:n])
}
return nil
}

type DataLoader struct {
data   []Item
mtx    sync.RWMutex
loaded bool
}
 
func (dl *DataLoader) ensureLoaded() {
dl.mtx.RLock()
loaded := dl.loaded
dl.mtx.RUnlock()
 
if !loaded {
    dl.mtx.Lock()
    defer dl.mtx.Unlock()
    if !dl.loaded { // повторная проверка после блокировки
        dl.data = loadItems() // потенциально тяжёлая операция
        dl.loaded = true
    }
}
}
 
func (dl *DataLoader) GetItems() []Item {
dl.ensureLoaded()
dl.mtx.RLock()
defer dl.mtx.RUnlock()
return slices.Clone(dl.data) // возвращаем копию для безопасности
}

type RingBuffer struct {
data []float64
size int
head int
tail int
full bool
}
 
func NewRingBuffer(size int) *RingBuffer {
return &RingBuffer{
    data: make([]float64, size),
    size: size,
}
}
 
func (rb *RingBuffer) Push(value float64) {
rb.data[rb.head] = value
rb.head = (rb.head + 1) % rb.size
 
if rb.head == rb.tail {
    rb.tail = (rb.tail + 1) % rb.size
    rb.full = true
}
 
if rb.full {
    rb.full = false
}
}
 
func (rb *RingBuffer) GetValues() []float64 {
result := make([]float64, 0, rb.size)
for i := 0; i < rb.size; i++ {
    idx := (rb.tail + i) % rb.size
    if idx == rb.head && !rb.full {
        break
    }
    result = append(result, rb.data[idx])
}
return result
}

func defragmentStorage(data [][]byte) [][]byte {
totalSize := 0
for _, item := range data {
    totalSize += len(item)
}
 
// Выделяем один непрерывный блок памяти
consolidated := make([]byte, totalSize)
result := make([][]byte, len(data))
 
offset := 0
for i, item := range data {
    copy(consolidated[offset:offset+len(item)], item)
    // Создаём слайс, указывающий на часть consolidated
    result[i] = consolidated[offset : offset+len(item)]
    offset += len(item)
}
 
return result
}

// Очередь с приоритетом на основе слайса
type PriorityQueue struct {
items []Item
less  func(a, b Item) bool
}
 
func (pq *PriorityQueue) Push(item Item) {
pq.items = append(pq.items, item)
i := len(pq.items) - 1
// Поднимаем элемент вверх, пока он не окажется на своём месте
for i > 0 {
    parent := (i - 1) / 2
    if !pq.less(pq.items[i], pq.items[parent]) {
        break
    }
    pq.items[i], pq.items[parent] = pq.items[parent], pq.items[i]
    i = parent
}
}
 
func (pq *PriorityQueue) Pop() (Item, bool) {
if len(pq.items) == 0 {
    var zero Item
    return zero, false
}
 
result := pq.items[0]
last := len(pq.items) - 1
pq.items[0] = pq.items[last]
pq.items = pq.items[:last]
 
// Опускаем корень вниз, восстанавливая свойства кучи
i := 0
for {
    smallest := i
    left := 2*i + 1
    right := 2*i + 2
    
    if left < len(pq.items) && pq.less(pq.items[left], pq.items[smallest]) {
        smallest = left
    }
    if right < len(pq.items) && pq.less(pq.items[right], pq.items[smallest]) {
        smallest = right
    }
    
    if smallest == i {
        break
    }
    
    pq.items[i], pq.items[smallest] = pq.items[smallest], pq.items[i]
    i = smallest
}
 
return result, true
}

// Неоптимально: будет расти экспоненциально с перераспределениями
data := make([]int, 0)
for i := 0; i < 10000; i++ {
    data = append(data, i)
}
 
// Оптимально: одна аллокация нужного размера
data := make([]int, 0, 10000)
for i := 0; i < 10000; i++ {
    data = append(data, i)
}

// Увеличиваем ёмкость с запасом
if cap(s) < needed {
    newCap := cap(s) * 2
    if newCap < needed {
        newCap = needed
    }
    newSlice := make([]T, len(s), newCap)
    copy(newSlice, s)
    s = newSlice
}
 
// Сжимаем только если использование меньше 25%
if cap(s) > 4*len(s) && cap(s) > 32 {
    newSlice := make([]T, len(s), cap(s)/2)
    copy(newSlice, s)
    s = newSlice
}

// После существенного уменьшения размера
if float64(len(s)) < 0.5*float64(cap(s)) {
    s = slices.Clip(s)
}

// НЕПРАВИЛЬНО: результат append не используется
slice := []int{1, 2, 3}
append(slice, 4) // slice не изменился!
 
// ПРАВИЛЬНО
slice = append(slice, 4)

// Потенциально опасный код
for i, v := range slice {
    if someCondition(v) {
        slice = append(slice[:i], slice[i+1:]...) // Удаляем текущий элемент
        // НО: range использует копию длины слайса, созданную в начале,
        // а индексы меняются при каждом удалении!
    }
}
 
// Безопасный подход: итерируем в обратном порядке
for i := len(slice) - 1; i >= 0; i-- {
    if someCondition(slice[i]) {
        slice = append(slice[:i], slice[i+1:]...)
    }
}

func process(data []int) {
    data = append(data, 999) // Это не изменит оригинальный слайс!
}
 
// Правильные подходы:
func process(data *[]int) {
    *data = append(*data, 999) // Изменяет оригинальный слайс
}
 
// Или возвращаем новый слайс
func process(data []int) []int {
    return append(data, 999)
}

import "testing"
 
func BenchmarkSliceOperations(b *testing.B) {
    for i := 0; i < b.N; i++ {
        data := make([]int, 0, 1000)
        for j := 0; j < 1000; j++ {
            data = append(data, j)
        }
    }
}

go test -bench=. -benchmem

go test -bench=. -memprofile=mem.out
go tool pprof mem.out

type SliceBuilder[T any] struct {
    data []T
}
 
func (b *SliceBuilder[T]) Add(item T) *SliceBuilder[T] {
    b.data = append(b.data, item)
    return b
}
 
func (b *SliceBuilder[T]) AddMany(items ...T) *SliceBuilder[T] {
    b.data = append(b.data, items...)
    return b
}
 
func (b *SliceBuilder[T]) Build() []T {
    return slices.Clone(b.data)
}

// Плохо: много преобразований
nums := []int{1, 2, 3}
strs := make([]string, 0, len(nums))
for _, n := range nums {
    strs = append(strs, fmt.Sprintf("%d", n))
}
ints := make([]int, 0, len(strs))
for _, s := range strs {
    n, _ := strconv.Atoi(s)
    ints = append(ints, n)
}
 
// Лучше: избегаем лишних преобразований

type Collection interface {
    Add(item interface{})
    Get(index int) interface{}
    Len() int
}
 
type GenericSlice[T any] struct {
    data []T
}
 
func (s *GenericSlice[T]) Add(item T) {
    s.data = append(s.data, item)
}
 
func (s *GenericSlice[T]) Get(index int) T {
    return s.data[index]
}
 
func (s *GenericSlice[T]) Len() int {
    return len(s.data)
}

type Mapper[T, U any] interface {
    Map(func(T) U) []U
}
 
func (s *GenericSlice[T]) Map[U any](f func(T) U) []U {
    result := make([]U, len(s.data))
    for i, v := range s.data {
        result[i] = f(v)
    }
    return result
}

// Преобразование слайса из одного типа в другой
func Map[T, U any](s []T, f func(T) U) []U {
    result := make([]U, len(s))
    for i, v := range s {
        result[i] = f(v)
    }
    return result
}
 
// Фильтрация слайса
func Filter[T any](s []T, f func(T) bool) []T {
    result := make([]T, 0, len(s))
    for _, v := range s {
        if f(v) {
            result = append(result, v)
        }
    }
    return result
}
 
// Группировка элементов слайса по ключу
func GroupBy[T any, K comparable](s []T, keyFunc func(T) K) map[K][]T {
    result := make(map[K][]T)
    for _, v := range s {
        key := keyFunc(v)
        result[key] = append(result[key], v)
    }
    return result
}

type CircularBuffer[T any] struct {
    buffer []T
    size   int
    start  int
    count  int
}
 
func NewCircularBuffer[T any](size int) *CircularBuffer[T] {
    return &CircularBuffer[T]{
        buffer: make([]T, size),
        size:   size,
    }
}
 
func (cb *CircularBuffer[T]) Add(item T) {
    position := (cb.start + cb.count) % cb.size
    
    if cb.count == cb.size {
        cb.start = (cb.start + 1) % cb.size
    } else {
        cb.count++
    }
    
    cb.buffer[position] = item
}
 
func (cb *CircularBuffer[T]) Get() []T {
    result := make([]T, cb.count)
    for i := 0; i < cb.count; i++ {
        position := (cb.start + i) % cb.size
        result[i] = cb.buffer[position]
    }
    return result
}

// Бинарная куча (для приоритетной очереди)
type BinaryHeap[T any] struct {
    data []T
    less func(T, T) bool
}
 
func (h *BinaryHeap[T]) Push(item T) {
    h.data = append(h.data, item)
    h.siftUp(len(h.data) - 1)
}
 
func (h *BinaryHeap[T]) Pop() (T, bool) {
    if len(h.data) == 0 {
        var zero T
        return zero, false
    }
    
    root := h.data[0]
    lastIdx := len(h.data) - 1
    h.data[0] = h.data[lastIdx]
    h.data = h.data[:lastIdx]
    
    if len(h.data) > 0 {
        h.siftDown(0)
    }
    
    return root, true
}
 
func (h *BinaryHeap[T]) siftUp(idx int) {
    for idx > 0 {
        parentIdx := (idx - 1) / 2
        if !h.less(h.data[idx], h.data[parentIdx]) {
            break
        }
        h.data[idx], h.data[parentIdx] = h.data[parentIdx], h.data[idx]
        idx = parentIdx
    }
}
 
func (h *BinaryHeap[T]) siftDown(idx int) {
    lastIdx := len(h.data) - 1
    for {
        leftIdx := 2*idx + 1
        rightIdx := 2*idx + 2
        smallest := idx
        
        if leftIdx <= lastIdx && h.less(h.data[leftIdx], h.data[smallest]) {
            smallest = leftIdx
        }
        if rightIdx <= lastIdx && h.less(h.data[rightIdx], h.data[smallest]) {
            smallest = rightIdx
        }
        
        if smallest == idx {
            break
        }
        
        h.data[idx], h.data[smallest] = h.data[smallest], h.data[idx]
        idx = smallest
    }
}

type SparseArray[T comparable] struct {
    size      int
    zeroValue T
    data      map[int]T
}
 
func NewSparseArray[T comparable](size int, zeroValue T) *SparseArray[T] {
    return &SparseArray[T]{
        size:      size,
        zeroValue: zeroValue,
        data:      make(map[int]T),
    }
}
 
func (sa *SparseArray[T]) Set(index int, value T) bool {
    if index < 0 || index >= sa.size {
        return false
    }
    
    if value == sa.zeroValue {
        delete(sa.data, index) // Не храним значения по умолчанию
    } else {
        sa.data[index] = value
    }
    return true
}
 
func (sa *SparseArray[T]) Get(index int) T {
    if index < 0 || index >= sa.size {
        return sa.zeroValue
    }
    
    if value, exists := sa.data[index]; exists {
        return value
    }
    return sa.zeroValue
}
 
func (sa *SparseArray[T]) ToSlice() []T {
    result := make([]T, sa.size)
    for i := range result {
        result[i] = sa.zeroValue
    }
    
    for idx, val := range sa.data {
        result[idx] = val
    }
    return result
}

// Сравнение работы с разными структурами данных
func BenchmarkDataStructures(b *testing.B) {
    const size = 10_000_000
    
    b.Run("LinkedList", func(b *testing.B) {
        // Создание связного списка
        var head *Node
        for i := 0; i < size; i++ {
            newNode := &Node{Value: i}
            if head == nil {
                head = newNode
            } else {
                current := head
                for current.Next != nil {
                    current = current.Next
                }
                current.Next = newNode
            }
        }
        
        // Измерение суммирования
        b.ResetTimer()
        sum := 0
        current := head
        for current != nil {
            sum += current.Value
            current = current.Next
        }
    })
    
    b.Run("Slice", func(b *testing.B) {
        // Создание слайса
        data := make([]int, size)
        for i := 0; i < size; i++ {
            data[i] = i
        }
        
        // Измерение суммирования
        b.ResetTimer()
        sum := 0
        for _, v := range data {
            sum += v
        }
    })
}

// Разделение данных по принципу SoA (Structure of Arrays)
// вместо традиционного AoS (Array of Structures)
type PersonAoS struct {
    ID   int
    Name string
    Age  int
}
 
type PersonsSoA struct {
    IDs   []int
    Names []string
    Ages  []int
}
 
func ProcessAges(people []PersonAoS) int {
    sum := 0
    for i := range people {
        sum += people[i].Age
    }
    return sum
}
 
func ProcessAgesSoA(people PersonsSoA) int {
    sum := 0
    for i := range people.Ages {
        sum += people.Ages[i]
    }
    return sum
}