Двоичная куча: интерактивная анимация (Binary Heap)

#include <stdio.h>
#include <stdlib.h>

// Структура для представления Min-Heap (Двоичной кучи на минимум)
typedef struct {
    int* data;      // Указатель на массив элементов
    int size;       // Текущее количество элементов в куче
    int capacity;   // Максимальная вместимость массива
} MinHeap;

// Вспомогательная функция для обмена значений двух элементов
void swap(int* a, int* b) {
    int t = *a; *a = *b; *b = t;
}

// Просеивание вверх (sift-up) - используется при вставке нового элемента.
// Поднимает элемент вверх по дереву, пока он меньше своего родителя.
void siftUp(MinHeap* heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2; // Вычисляем индекс родителя
        // Если текущий элемент меньше родителя, меняем их местами
        if (heap->data[i] < heap->data[parent]) {
            swap(&heap->data[i], &heap->data[parent]);
            i = parent; // Переходим к родителю
        } else {
            break; // Свойство кучи восстановлено
        }
    }
}

// Просеивание вниз (sift-down) - используется при извлечении минимума.
// Опускает элемент вниз по дереву, меняясь с наименьшим из потомков.
void siftDown(MinHeap* heap, int i) {
    // Пока есть хотя бы левый потомок
    while (2 * i + 1 < heap->size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int minIdx = i;

        // Ищем индекс минимального элемента среди родителя и его потомков
        if (heap->data[left] < heap->data[minIdx]) minIdx = left;
        if (right < heap->size && heap->data[right] < heap->data[minIdx]) minIdx = right;

        // Если родитель не минимален, меняем его с наименьшим потомком
        if (minIdx != i) {
            swap(&heap->data[i], &heap->data[minIdx]);
            i = minIdx; // Продолжаем просеивание от нового индекса
        } else {
            break; // Элемент на своем месте
        }
    }
}

// Вставка нового значения в кучу
void insert(MinHeap* heap, int val) {
    if (heap->size == heap->capacity) return; // Проверка на переполнение

    // Добавляем элемент в конец массива (как правый нижний лист дерева)
    heap->data[heap->size] = val;
    heap->size++;

    // Восстанавливаем свойство кучи просеиванием вверх
    siftUp(heap, heap->size - 1);
}

// Извлечение минимального элемента (находится в корне)
int extractMin(MinHeap* heap) {
    if (heap->size == 0) return -1; // Очередь пуста

    int minVal = heap->data[0]; // Минимум всегда в корне

    // Ставим последний элемент дерева на место корня
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;

    // Восстанавливаем свойство кучи просеиванием вниз от корня
    if (heap->size > 0) {
        siftDown(heap, 0);
    }

    return minVal;
}

class MinHeap:
    def __init__(self):
        self.data = [] # В Python списки динамические, вместимость не фиксируем

    def insert(self, val):
        # Добавляем новый элемент в конец массива
        self.data.append(val)
        # Восстанавливаем свойство кучи, просеивая элемент вверх
        self._sift_up(len(self.data) - 1)

    def extract_min(self):
        if not self.data:
            return None # Куча пуста

        min_val = self.data[0] # Минимум всегда находится в корне

        # Переносим последний элемент в корень и удаляем его с конца
        self.data[0] = self.data[-1]
        self.data.pop()

        # Если куча не опустела, восстанавливаем ее просеиванием вниз
        if self.data:
            self._sift_down(0)

        return min_val

    def _sift_up(self, i):
        # Поднимаем элемент вверх, пока он не достигнет корня
        while i > 0:
            parent = (i - 1) // 2 # Вычисляем индекс родителя
            # Если элемент меньше родителя, меняем их местами
            if self.data[i] < self.data[parent]:
                self.data[i], self.data[parent] = self.data[parent], self.data[i]
                i = parent
            else:
                break # Свойство кучи выполнено

    def _sift_down(self, i):
        size = len(self.data)
        # Пока у узла есть хотя бы один (левый) потомок
        while 2 * i + 1 < size:
            left = 2 * i + 1
            right = 2 * i + 2
            min_idx = i

            # Находим индекс минимального из родителя и детей
            if self.data[left] < self.data[min_idx]:
                min_idx = left
            if right < size and self.data[right] < self.data[min_idx]:
                min_idx = right

            # Если родитель больше потомка, меняем их местами
            if min_idx != i:
                self.data[i], self.data[min_idx] = self.data[min_idx], self.data[i]
                i = min_idx
            else:
                break # Узел на своем месте

class MinHeap {
    constructor() {
        this.data = []; // В JS массивы динамические
    }

    insert(val) {
        // Добавляем элемент в конец (как последний лист дерева)
        this.data.push(val);
        // Вызываем просеивание вверх для восстановления свойства кучи
        this.siftUp(this.data.length - 1);
    }

    extractMin() {
        if (this.data.length === 0) return null; // Очередь пуста

        let minVal = this.data[0]; // Корень содержит минимальный элемент

        // Заменяем корень последним элементом и удаляем последний
        this.data[0] = this.data[this.data.length - 1];
        this.data.pop();

        // Просеиваем новый корень вниз, чтобы восстановить структуру
        if (this.data.length > 0) {
            this.siftDown(0);
        }
        return minVal;
    }

    siftUp(i) {
        while (i > 0) {
            let parent = Math.floor((i - 1) / 2); // Индекс родителя

            // Если потомок меньше родителя - меняем их (свойство Min-Heap)
            if (this.data[i] < this.data[parent]) {
                // Синтаксис деструктуризации для быстрого обмена значений
                [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
                i = parent; // Двигаемся вверх
            } else {
                break; // Свойство кучи не нарушено
            }
        }
    }

    siftDown(i) {
        let size = this.data.length;
        // Пока есть хотя бы левый потомок
        while (2 * i + 1 < size) {
            let left = 2 * i + 1;
            let right = 2 * i + 2;
            let minIdx = i;

            // Ищем минимум среди родителя и доступных потомков
            if (this.data[left] < this.data[minIdx]) minIdx = left;
            if (right < size && this.data[right] < this.data[minIdx]) minIdx = right;

            // Если минимальный элемент - это один из потомков, меняемся
            if (minIdx !== i) {
                [this.data[i], this.data[minIdx]] = [this.data[minIdx], this.data[i]];
                i = minIdx; // Продолжаем спуск
            } else {
                break; // Элемент опустился на правильное место
            }
        }
    }
}