Узнайте, как реализовать минимальную кучу в Typescript
Понятия не имею, почему, но на днях я искал JS-реализации кучи. Я не мог найти никого, кто бы их написал в удобочитаемой форме. Все было написано на C ++, Python или Java.
Самый близкий, который мне удалось найти, написал Анкита Масанд. Она очень хорошо объяснила, что такое кучи и чего они пытаются достичь. Лично я, однако, не был уверен, что все понял, поэтому подумал, что напишу свою собственную реализацию в надежде прояснить собственное понимание.
Начнем с объявления нашего класса в Typescript с нашей поддерживающей структурой данных, представляющей собой массив чисел.
export class MinimumHeap {
public heap: Array<number> = new Array<number>();
constructor() { }
}
Достаточно просто, теперь перейдем к добавлению элемента в кучу. Ниже приведен аналогичный пример того, что использовала Анкита.
Проще говоря, всякий раз, когда мы добавляем элемент, мы всегда пытаемся заполнить самое левое доступное место на дереве. Затем мы всплываем наш элемент, если только что добавленный элемент меньше нашего родительского. Итак, давайте посмотрим на это в коде.
В отличие от Анкиты, я буду использовать индекс на основе 0 для хранения моей кучи. Эта математика не намного сложнее, и нам не нужно видеть пустое место в нашем массиве.
Используя деструктуризацию ES2016, я реализую функцию подкачки в моем классе кучи, как показано ниже.
Есть и другие способы поменять местами 2 числа, но в данном случае я воспользуюсь синтаксическим сахаром, чтобы сделать это лучше.
Итак, легкая часть теперь позади. Давайте немного передохнем, прежде чем перейдем к коду, требующему немного больше размышлений.
Вот ситуация для удаления узла из верхней части минимальной кучи.
Проще говоря, элемент заголовка массива «удаляется» и заменяется самым последним моментом в массиве. Затем элемент, который мы переместили в заголовок массива, необходимо скопировать до тех пор, пока он не займет правильное положение.
Поскольку это минимальная куча, мы посмотрим, больше ли родительский узел, чем его дочерние элементы. Самые большие предметы уходят в нижнюю часть дерева, а самые маленькие остаются наверху.
Итак, вот оно. Самая сложная часть этой структуры данных кучи. Найдите время, чтобы понять эту реализацию. Он немного отличается от структуры Анкиты, однако мы делаем именно то, что она делает, с меньшим количеством заявлений.
Вот несколько ключевых отличий:
- Индекс на основе 0 для массива
- Цикл Do-While позволяет нам выполнять даже начальные вычисления без дополнительных условий / операторов.
- Дочерний узел теперь рассчитывается по формуле left = 2 * parent + 1 и right = 2 * parent + 2.
Источник
