Поиск по сайту:

Двоичные кучи и приоритетные очереди через JavaScript


Хотя я уверен, что мы все можем согласиться с тем, что деревья называются кучами. С помощью кучи мы можем структурировать наши данные в более интеллектуальную очередь, которая сортируется по важности, а не по порядку.

Концепции

В отличие от бинарных деревьев поиска, где мы сравнивали и упорядочивали наши значения для братьев и сестер, с кучами мы работаем только между родителями и их детьми. Это дает нам две возможности для куч: max heap и min heap, в зависимости от того, двигаетесь ли вы от самых высоких значений к самым низким или наоборот. Для простоты мы сосредоточимся только на максимальной куче, так как ее очень легко преобразовать в минимальную кучу.

Как и в случае с бинарными деревьями поиска, бинарные кучи могут иметь только двух или менее дочерних элементов для родителя. Они также особенные, поскольку они всегда сбалансированы, потому что каждый новый узел будет добавляться на уровень слева направо до полного заполнения.

К сожалению, связанные списки, как правило, не лучший подход к двоичным кучам, несмотря на то, что обычно они представляются как дерево с левыми и правыми дочерними элементами, хотя это все же возможно.

В большинстве случаев будет лучше обращаться с ним как с массивом, так что это то, что мы собираемся рассмотреть здесь. Порядок такой, как и следовало ожидать, все слева направо на уровне перед переходом на следующий уровень.

Таким образом, мы создаем очень последовательный шаблон для поиска дочерних элементов узла. Все левые дочерние элементы узла будут точно в позиции 2n + 1 от своего родителя, где n будет индексом их родителя, а все правые дочерние элементы будут 2n + 2.

Добавить узел

Казалось бы, добавление нового узла будет таким же простым, как добавление в наш массив, но сложная часть заключается в том, что нам нужно сравнить его с родителями между ним и максимальным, а затем соответствующим образом изменить их порядок.

Графика/анимация благодаря VisuAlgo.net

После того, как мы поместим наш новый элемент в конец массива, нам нужно «поднять» наши большие значения. Во-первых, нам нужно захватить новый элемент в конце массива, который мы разобьем на индекс и новый элемент по этому индексу.

Каждый раз, когда мы добавляем элемент, мы будем использовать обратное уравнение для поиска дочерних элементов, (n-1)/2, чтобы найти его родителя. Если его родитель меньше текущего узла, поменяйте их местами, затем сохраните его индекс, который будет следующим current. Так будет продолжаться до тех пор, пока не останется родителей.

Поскольку он будет постепенно перемещать наш index вверх с конца, пока он больше нуля, продолжайте менять местами.

class BH {
  constructor() {
    this.values = [];
  }
  add(element) {
    this.values.push(element);
    let index = this.values.length - 1;
    const current = this.values[index];

    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.values[parentIndex];

      if (parent <= current) {
        this.values[parentIndex] = current;
        this.values[index] = parent;
        index = parentIndex;
      } else break;
    }
  }
}

const tree = new BH();
tree.add(3);
tree.add(4);
tree.add(31);
tree.add(6);
console.log(tree); // [31, 6, 4, 3]

Удалить Макс

Удаление самого верхнего узла немного сложнее, чем вы думаете. Мы собираемся вернуть первый узел, наш максимум, затем взять последний узел, конец нашего массива, и установить его как новый максимум.

Мы делаем это, чтобы мы могли использовать наше самое низкое значение в качестве простой основы для сравнения с другими нашими значениями, поскольку мы «опускаемся» обратно в нижнюю часть дерева, выполняя наши сравнения и обмены по пути.

Графика/анимация благодаря VisuAlgo.net

Простая часть заключается в том, чтобы получить наше текущее максимальное значение и удалить его, прежде чем заменить его последним элементом, после чего мы можем вернуть исходное максимальное значение после того, как все остальное будет сделано.

Когда у нас есть начальный индекс, мы хотим получить как его правый, так и левый дочерние элементы. Если левый дочерний элемент является допустимым элементом и больше, мы можем сохранить его как swap, чтобы запустить обмен, когда все сравнения будут выполнены.

Правильный дочерний элемент немного сложнее, мы хотим, чтобы только один и самый большой дочерний элемент был заменен на родителя. Мы добавим отдельное требование, чтобы rightChild мог быть установлен как swap только в том случае, если он еще не определен или больше, чем leftChild.

class BH {
  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    this.values[0] = end;

    let index = 0;
    const length = this.values.length;
    const current = this.values[0];
    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.values[leftChildIndex];
        if (leftChild > current) swap = leftChildIndex;
      }
      if (rightChildIndex < length) {
        rightChild = this.values[rightChildIndex];
        if (
          (swap === null && rightChild > current) ||
          (swap !== null && rightChild > leftChild)
        )
          swap = rightChildIndex;
      }

      if (swap === null) break;
      this.values[index] = this.values[swap];
      this.values[swap] = current;
      index = swap;
    }

    return max;
  }
}

const tree = new BH();
tree.add(3);
tree.add(4);
tree.add(31);
tree.add(6);
console.log(tree.extractMax()); // 31

Приоритетные очереди

С помощью нескольких незначительных изменений мы можем смешивать двоичные кучи с очередями и создавать очередь, которая упорядочивает наши данные по важности, а не по дате добавления.

Мы можем добиться этого достаточно просто, сохраняя узлы вместо отдельных чисел. У каждого узла будет уровень приоритета (скажем, от 1 до 5), который он будет использовать для определения порядка. Когда приоритеты на двух узлах одинаковы, левый дочерний элемент, поскольку он будет добавлен первым, будет идти первым.

Все, что нам нужно сделать, это использовать priority узла каждый раз, когда мы делаем сравнение в операторе if.

class Node {
  constructor(val, priority) {
    this.val = val;
    this.priority = priority;
  }
}

class PQ {
  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    let newNode = new Node(val, priority);
    this.values.push(newNode);
    let index = this.values.length - 1;
    const current = this.values[index];

    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.values[parentIndex];

      if (parent.priority <= current.priority) {
        this.values[parentIndex] = current;
        this.values[index] = parent;
        index = parentIndex;
      } else break;
    }
  }
  dequeue() {
    const max = this.values[0];
    const end = this.values.pop();
    this.values[0] = end;

    let index = 0;
    const length = this.values.length;
    const current = this.values[0];
    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.values[leftChildIndex];
        if (leftChild.priority > current.priority) swap = leftChildIndex;
      }
      if (rightChildIndex < length) {
        rightChild = this.values[rightChildIndex];
        if (
          (swap === null && rightChild.priority > current.priority) ||
          (swap !== null && rightChild.priority > leftChild.priority)
        )
          swap = rightChildIndex;
      }

      if (swap === null) break;
      this.values[index] = this.values[swap];
      this.values[swap] = current;
      index = swap;
    }

    return max;
  }
}

const tree = new BH();
tree.enqueue(3, 2);
tree.enqueue(4, 5);
tree.enqueue(31, 1);
tree.enqueue(6, 3);
console.log(tree.dequeue()); // 4
console.log(tree.dequeue()); // 6
console.log(tree.dequeue()); // 3
console.log(tree.dequeue()); // 31

Заключительные мысли

Точно так же, как мы использовали стандартные очереди для обхода дерева, приоритетные очереди будут необходимы для интеллектуального обхода графов и более сложных структур.

Преобразование максимальной кучи в минимальную кучу так же просто, как изменение нашего знака «больше» на «меньше» во всех наших сравнениях.