Операции с кучей

      1
      function siftUp(heap, index) {
    

      2
      // Повторно обменивайтесь с родителем, пока свойство кучи не будет восстановлено или не будет достигнут корень
    

      3
      while (index > 0) {
    

      4
        const parentIndex = Math.floor((index - 1) / 2);
    

      5
        // В мин-куче, ребёнок < родитель — нарушение; обмен и продолжение
    

      6
        if (heap[index] < heap[parentIndex]) {
    

      7
          [heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]];
    

      8
          index = parentIndex;
    

      9
        } else {
    

      10
          break; // Свойство кучи восстановлено
    

      11
        }
    

      12
      }
    

      13
      }
    

      14
       
    

      15
      function push(heap, value) {
    

      16
      heap.push(value);
    

      17
      siftUp(heap, heap.length - 1);
    

      18
      }
    

• L1 Просеивание вверх восстанавливает свойство кучи после вставки.
• L3 Продолжайте, пока узел не является корнем.
• L4 Вычислите индекс родителя, используя стандартную формулу.
• L6 В мин-куче, если ребёнок < родитель, свойство нарушено.
• L7 Обменяйте ребёнка с родителем и движение вверх.
• L10 Push добавляет значение в конец и просеивает его вверх.

      1
      function siftDown(heap, index) {
    

      2
      // Повторно обменивайтесь с меньшим (или большим) ребёнком, пока свойство будет выполнено
    

      3
      while (true) {
    

      4
        const leftChild = 2 * index + 1;
    

      5
        const rightChild = 2 * index + 2;
    

      6
        let smallest = index;
    

      7
        
    

      8
        // Проверьте, существует ли левый ребёнок и меньше ли он текущего наименьшего
    

      9
        if (leftChild < heap.length && heap[leftChild] < heap[smallest]) {
    

      10
          smallest = leftChild;
    

      11
        }
    

      12
        
    

      13
        // Проверьте, существует ли правый ребёнок и меньше ли он
    

      14
        if (rightChild < heap.length && heap[rightChild] < heap[smallest]) {
    

      15
          smallest = rightChild;
    

      16
        }
    

      17
        
    

      18
        // Если ребёнок меньше, обмен и продолжение; иначе стоп
    

      19
        if (smallest !== index) {
    

      20
          [heap[index], heap[smallest]] = [heap[smallest], heap[index]];
    

      21
          index = smallest;
    

      22
        } else {
    

      23
          break; // Свойство кучи восстановлено
    

      24
        }
    

      25
      }
    

      26
      }
    

      27
       
    

      28
      function pop(heap) {
    

      29
      const root = heap[0];
    

      30
      heap[0] = heap[heap.length - 1];
    

      31
      heap.pop();
    

      32
      if (heap.length > 0) {
    

      33
        siftDown(heap, 0);
    

      34
      }
    

      35
      return root;
    

      36
      }
    

• L1 Просеивание вниз восстанавливает свойство кучи после удаления корня.
• L4 Вычислите индексы левого и правого детей.
• L5 Отслеживайте индекс наименьшего элемента (для мин-кучи).
• L8 Если левый ребёнок существует и меньше, обновите наименьший.
• L13 Проверьте правый ребёнок так же.
• L18 Если наименьший не текущий узел, обмен необходим.
• L19 Обменяйте и продолжайте просеивание с новой позиции.
• L24 Pop возвращает корень и восстанавливает свойство кучи.

      1
      function buildHeap(arr) {
    

      2
      // Начните с последнего не-листового узла и просейте вниз каждый
    

      3
      const lastNonLeaf = Math.floor(arr.length / 2) - 1;
    

      4
      for (let i = lastNonLeaf; i >= 0; i--) {
    

      5
        siftDown(arr, i);
    

      6
      }
    

      7
      return arr;
    

      8
      }
    

      9
       
    

      10
      // Пример: превратить неупорядоченный массив в мин-кучу
    

      11
      const unordered = [5, 3, 8, 1, 4];
    

      12
      buildHeap(unordered);
    

      13
      console.log("Куча:", unordered); // [1, 3, 8, 5, 4]
    

• L1 buildHeap преобразует любой массив в валидную кучу.
• L3 Последний не-листовый узел на индексе floor(n/2) - 1.
• L4 Повторяйте от последнего не-листового до корня (индекс 0).
• L5 Просейте вниз каждый узел, чтобы восстановить свойство кучи в его поддереве.
• L11 buildHeap — O(n), потому что большинство узлов листья (O(1) просеивание) и внутренние узлы имеют короткие поддеревья.