<section id="description">
<p>Вероятно, вы знакомы со стопкой книг на своем столе. Вероятно, вы использовали функцию отмены текстового редактора. Вы также, вероятно, используете для нажатия кнопки «Назад» на своем телефоне, чтобы вернуться к предыдущему виду в приложении. Вы знаете, что у них общего? Все они хранят данные таким образом, чтобы вы могли перемещаться назад. Самая верхняя книга в стеке была той, которая была помещена последней. Если вы удалите эту книгу из верхней части стека, вы откроете книгу, которая была помещена туда до последней книги, и так далее. Если вы думаете об этом, во всех приведенных выше примерах вы получаете тип обслуживания <dfn>Last-In-First-Out</dfn> . Мы постараемся имитировать это с помощью нашего кода. Эта схема хранения данных называется <dfn>стеком</dfn> . В частности, нам пришлось бы реализовать метод <code>push()</code> который толкает объекты JavaScript вверху стека; и <code>pop()</code> , который удаляет объект JavaScript, который находится в верхней части стека в текущий момент.</p></section>

Learn how a Stack Works

<section id="description">
<p>В последнем разделе мы говорили о том, что такое стек и как мы можем использовать массив для представления стека. В этом разделе мы создадим собственный класс стека. Хотя вы можете использовать массивы для создания стеков, иногда лучше ограничивать количество контроля, которое у нас есть с нашими стопами. Помимо метода <code>push</code> и <code>pop</code> , у стеков есть и другие полезные методы. Давайте добавим <code>peek</code> , <code>isEmpty</code> и <code>clear</code> метод в наш класс стека. Инструкции Напишите метод <code>push</code> который подталкивает элемент к вершине стека, метод <code>pop</code> который удаляет элемент в верхней части стека, метод <code>peek</code> который смотрит на первый элемент в стеке, метод <code>isEmpty</code> который проверяет, стек пуст и <code>clear</code> метод, который удаляет все элементы из стека. Обычно у стеков это не так, но мы добавили метод вспомогательной <code>print</code> котором консоль регистрирует коллекцию.</p></section>

Create a Stack Class

<section id="description">
<p>Как и стеки, очереди представляют собой набор элементов. Но, в отличие от стеков, очереди следуют принципу FIFO (First-In First-Out). Элементы, добавленные в очередь, помещаются в хвост или конец очереди, и только элемент в передней части очереди разрешен для удаления. Мы могли бы использовать массив для представления очереди, но точно так же, как стеки, мы хотим ограничить количество контроля над нашими очередями. Двумя основными методами класса очереди являются метод enqueue и dequeue. Метод enqueue подталкивает элемент к хвосту очереди, а метод dequeue удаляет и возвращает элемент в передней части очереди. Другими полезными методами являются методы front, size и isEmpty. Инструкции. Напишите метод enqueue, который подталкивает элемент к хвосту очереди, метод dequeue, который удаляет и возвращает передний элемент, передний метод, который позволяет нам видеть передний элемент, метод размера, который показывает длину, и метод isEmpty чтобы проверить, пуста ли очередь.</p></section>

Create a Queue Class

<section id="description">
<p>Другой общей структурой данных, с которой вы столкнетесь в информатике, является <dfn>связанный список</dfn> . Связанный список представляет собой линейный набор элементов данных, называемый «узлами», каждый из которых указывает на следующий. Каждый <dfn>узел</dfn> в связанном списке содержит две ключевые части информации: сам <code>element</code> и ссылку на следующий <code>node</code> . Представьте, что вы находитесь в линии конги. У вас есть руки на следующем человеке в очереди, и человек, стоящий за вами, держит вас в руках. Вы можете видеть человека прямо перед собой, но они блокируют взгляд других людей в очереди. Узел точно так же, как человек в линии конги: они знают, кто они, и они могут видеть только следующего человека в очереди, но они не знают других людей впереди или позади них.</p></section>

Work with Nodes in a Linked List

<section id="description">
<p>Let's create a <code>linked list</code> class. Every linked list should start out with a few basic properties: a <code>head</code> (the first item in your list) and a <code>length</code> (number of items in your list). Sometimes you'll see implementations of linked lists that incorporate a <code>tail</code> for the last element of the list, but for now we'll just stick with these two. Whenever we add an element to the linked list, our <code>length</code> property should be incremented by one.</p>
<p>We'll want to have a way to add items to our linked list, so the first method we'll want to create is the <code>add</code> method.</p>
<p>If our list is empty, adding an element to our linked list is straightforward enough: we just wrap that element in a <code>Node</code> class, and we assign that node to the <code>head</code> of our linked list.</p>
<p>But what if our list already has one or more members? How do we add an element to the list? Recall that each node in a linked list has a <code>next</code> property. To add a node to the list, find the last node in the list, and point that last node's <code>next</code> property at our new node. (Hint: you know you've reached the end of a linked list when a node's <code>next</code> property is <code>null</code>.)</p></section>

Create a Linked List Class

<section id="description">
<p>Следующим важным методом, который потребуется для любой реализации связанного списка, является метод <code>remove</code> . Этот метод должен взять элемент, который мы хотим удалить в качестве аргумента, а затем выполнить поиск в списке, чтобы найти и удалить узел, содержащий этот элемент. Всякий раз, когда мы удаляем узел из связанного списка, важно, чтобы мы не случайно оставили все остальное в списке. Напомним, что <code>next</code> свойство <code>next</code> узла указывает на узел, который следует за ним в списке. Если мы удалим средний элемент, скажем, мы хотим убедиться , что у нас есть связь с предыдущим узлом этого элемента <code>next</code> имущества к середине элемента <code>next</code> имуществу (который является следующим узлом в списке!) Это может показаться действительно запутанный, так что давайте вернемся к примеру линии conga, чтобы у нас была хорошая концептуальная модель. Представьте себя в линии конги, и человек прямо перед вами покинет линию. Лицо, которое только что покинуло линию, больше не имеет руки на кого-либо в очереди - и у вас больше нет рук на лице, которое осталось. Вы шагнете вперед и положите руки на следующего человека, которого видите. Если элемент мы хотим , чтобы удалить это <code>head</code> элемент, мы переназначить <code>head</code> на второй узел связанного списка.</p></section>

Remove Elements from a Linked List

<section id="description">
<p>Давайте добавим еще несколько полезных методов в наш связанный класс списка. Не было бы полезно, если бы мы могли сказать, был ли наш список пустым или нет, как в наших классах <code>Stack</code> и <code>Queue</code> ? Мы также должны иметь возможность находить определенные элементы в нашем связанном списке. Прохождение через структуры данных - это то, с чем вы захотите получить много практики! Давайте создадим метод <code>indexOf</code> который принимает <code>element</code> в качестве аргумента и возвращает <code>index</code> этого элемента в связанном списке. Если элемент не найден в связанном списке, верните <code>-1</code> . Давайте также реализуем метод, который делает обратное: метод <code>elementAt</code> который принимает <code>index</code> в качестве аргумента и возвращает <code>element</code> в указанном <code>index</code> . Если ни один <code>element</code> не найден, возвращайте <code>undefined</code> .</p></section>

Search within a Linked List

<section id="description">
<p>Прежде чем перейти к другой структуре данных, давайте получим пару последних бит практики со связанными списками. Давайте напишем <code>removeAt</code> который удаляет <code>element</code> по заданному <code>index</code> . Метод следует называть <code>removeAt(index)</code> . Чтобы удалить <code>element</code> с определенным <code>index</code> , нам нужно сохранить количество запусков каждого узла при перемещении по связанному списку. Обычный метод, используемый для итерации через элементы связанного списка, включает в себя <dfn>«бегун»</dfn> или дозорный, который «указывает» на узлы, которые сравнивает ваш код. В нашем случае, начиная с <code>head</code> нашего списка, мы начинаем с переменной <code>currentIndex</code> которая начинается с <code>0</code> . <code>currentIndex</code> должен увеличиваться на единицу для каждого проходящего узла. Так же, как наш метод <code>remove(element)</code> , мы должны быть осторожны, чтобы не осилить остальную часть нашего списка, когда мы удаляем узел в нашем методе removeAt (index). Мы держим наши узлы смежными, убедившись, что узел, имеющий ссылку на удаленный узел, имеет ссылку на следующий узел.</p></section>

Remove Elements from a Linked List by Index

<section id="description">
<p>Давайте создадим метод addAt (index, element), который добавит элемент в данный индекс. Точно так же, как мы удаляем элементы с заданным индексом, нам нужно отслеживать currentIndex, когда мы пересекаем связанный список. Когда currentIndex соответствует указанному индексу, нам нужно переназначить следующее свойство предыдущего узла для ссылки на новый добавленный узел. И новый узел должен ссылаться на следующий узел в currentIndex. Возвращаясь к примеру линии conga, новый человек хочет присоединиться к линии, но он хочет присоединиться к середине. Вы находитесь в середине линии, поэтому вы отнимаете руки у человека впереди вас. Новый человек ходит и кладет руки на человека, которого вы когда-то держали, и теперь у вас есть руки на нового человека. Инструкции Создайте метод addAt (index, element), который добавляет элемент в данный индекс. Возвращает false, если элемент не может быть добавлен. Примечание. Не забудьте проверить, является ли данный индекс отрицательным или длиннее длины связанного списка.</p></section>

Add Elements at a Specific Index in a Linked List

<section id="description">
<p>Массивы - это объекты JavaScript, которые могут содержать множество разных элементов. <code>var complexArr = [1, 5, "2", "Word", {"name": "James"}];</code> В основном, что происходит в фоновом режиме, так это то, что ваш браузер автоматически предоставит необходимый объем памяти для этого массива. Он также будет изменяться по мере необходимости, если вы добавите или удалите данные. Тем не менее, в мире высокой производительности и разных типов элементов иногда требуется более конкретная информация о том, сколько памяти передано массиву. Ответы на эту проблему вызывают <dfn>типизированные массивы</dfn> . Теперь вы можете сказать, сколько памяти вы хотите дать массиву. Ниже представлен базовый обзор различных типов доступных массивов и размер в байтах для каждого элемента в этом массиве. <table class="table table-striped"><tbody><tr><th> Тип </th><th> Размер каждого элемента в байтах </th></tr><tr><td> <code>Int8Array</code> </td> <td> 1 </td></tr><tr><td> <code>Uint8Array</code> </td> <td> 1 </td></tr><tr><td> <code>Uint8ClampedArray</code> </td> <td> 1 </td></tr><tr><td> <code>Int16Array</code> </td> <td> 2 </td></tr><tr><td> <code>Uint16Array</code> </td> <td> 2 </td></tr><tr><td> <code>Int32Array</code> </td> <td> 4 </td></tr><tr><td> <code>Uint32Array</code> </td> <td> 4 </td></tr><tr><td> <code>Float32Array</code> </td> <td> 4 </td></tr><tr><td> <code>Float64Array</code> </td> <td> 8 </td></tr></tbody></table> Существует два способа создания таких массивов. Один из способов - создать его напрямую. Ниже <code>Int16Array</code> как создать <code>Int16Array</code> длиной 3 длины. <blockquote> var i8 = новый Int16Array (3); <br> console.log (i8); <br> // Возвращает [0, 0, 0] </blockquote> Вы также можете создать <dfn>буфер,</dfn> чтобы указать, сколько данных (в байтах) требуется массиву. <strong>Заметка</strong> <br> Чтобы создать типизированные массивы с использованием буферов, вам необходимо назначить количество байтов кратным байтам, перечисленным выше. <blockquote> // Создаем такой же массив Int16Array по-разному <br> var byteSize = 6; // Требуется быть кратным 2 <br> var buffer = new ArrayBuffer (byteSize); <br> var i8View = новый Int16Array (буфер); <br> buffer.byteLength; // Возвращает 6 <br> i8View.byteLength; // Возвращает 6 <br> console.log (i8View); // Возвращает [0, 0, 0] </blockquote> <dfn>Буферы</dfn> представляют собой объекты общего назначения, которые просто переносят данные. Вы не можете получить к ним доступ в обычном режиме. Чтобы получить к ним доступ, вам нужно сначала создать <dfn>представление</dfn> . <blockquote> i8View [0] = 42; <br> console.log (i8View); // Возвращает [42, 0, 0] </blockquote> <strong>Заметка</strong> <br> Типизированные массивы не имеют некоторых методов, которые имеют традиционные массивы, такие как <code>.pop()</code> или <code>.push()</code> . В типизированных массивах также отсутствует <code>Array.isArray()</code> который проверяет, что-то есть массив. Хотя это проще, это может быть преимуществом для менее сложных JavaScript-движков для их реализации.</p></section>

Typed Arrays

<section id="description">
<p>В этих упражнениях мы собираемся создать функцию удаления для нашего набора. Функция должна быть названа <code>this.remove</code> . Эта функция должна принимать значение и проверять, существует ли он в наборе. Если это так, удалите это значение из набора и верните true. В противном случае верните false.</p></section>

Remove from a Set

<section id="description">
<p>В этом упражнении мы собираемся выполнить объединение на двух наборах данных. Мы создадим метод в нашей структуре данных <code>Set</code> называемый <code>union</code> . Этот метод должен принимать другой <code>Set</code> в качестве аргумента и возвращать <code>union</code> двух наборов, исключая любые повторяющиеся значения. Например, если <code>setA = ['a','b','c']</code> и <code>setB = ['a','b','d','e']</code> , то объединение множества A и setB: <code>setA.union(setB) = ['a', 'b', 'c', 'd', 'e']</code> .</p></section>

Perform a Union on Two Sets

<section id="description">
<p>В этом упражнении мы собираемся выполнить пересечение на 2 набора данных. Мы создадим метод на наших <code>Set</code> структуры данных называется <code>intersection</code> . Пересечение множеств представляет все значения, которые являются общими для двух или более наборов. Этот метод должен принимать другой <code>Set</code> в качестве аргумента и возвращать <code>intersection</code> двух наборов. Например, если <code>setA = ['a','b','c']</code> и <code>setB = ['a','b','d','e']</code> , то пересечение множества A и множества B: <code>setA.intersection(setB) = ['a', 'b']</code> .</p></section>

Perform an Intersection on Two Sets of Data

<section id="description">
<p>В этом упражнении мы собираемся выполнить разницу на 2 набора данных. Мы создадим метод на нашем <code>Set</code> структуры данных называется <code>difference</code> . Разница множеств должна сравнивать два набора и возвращать элементы, присутствующие в первом наборе, отсутствующие во втором. Этот метод должен принять другой <code>Set</code> в качестве аргумента и вернуть <code>difference</code> двух наборов. Например, если <code>setA = ['a','b','c']</code> и <code>setB = ['a','b','d','e']</code> , то разность setA и setB равна: <code>setA.difference(setB) = ['c']</code> .</p></section>

Perform a Difference on Two Sets of Data

<section id="description">
<p>В этом упражнении мы собираемся выполнить тест подмножества на 2 набора данных. Мы создадим метод на нашем <code>Set</code> структуры данных называется <code>subset</code> . Это будет сравнивать первый набор, второй и если первый набор полностью содержится внутри второго, тогда он вернет true. Например, если <code>setA = ['a','b']</code> и <code>setB = ['a','b','c','d']</code> , то подмножество setA и setB будет: <code>setA.subset(setB)</code> должно быть <code>true</code> .</p></section>

Perform a Subset Check on Two Sets of Data

<section id="description">
<p>Теперь, когда вы работали с ES5, вы собираетесь выполнить что-то подобное в ES6. Это будет значительно проще. ES6 содержит встроенную структуру данных. <code>Set</code> операций, которые вы написали вручную, теперь включены для вас. Давайте посмотрим: Чтобы создать новый пустой набор: <code>var set = new Set();</code> Вы можете создать набор со значением: <code>var set = new Set(1);</code> Вы можете создать набор с массивом: <code>var set = new Set([1, 2, 3]);</code> Когда вы создали набор, вы можете добавить нужные значения с помощью метода <code>add</code> : <blockquote> var set = new Set ([1, 2, 3]); <br> set.add ([4, 5, 6]); </blockquote> Напомним, что набор представляет собой структуру данных, которая не может содержать повторяющиеся значения: <blockquote> var set = new Set ([1, 2, 3, 1, 2, 3]); <br> // set содержит только [1, 2, 3] </blockquote></p>
</section>

Create and Add to Sets in ES6

<section id="description">
<p>Давайте практикуем элементы removeimg из набора ES6, используя метод <code>delete</code> . Сначала создайте набор ES6 <code>var set = new Set([1,2,3]);</code> Теперь удалите элемент из вашего набора с помощью метода <code>delete</code> . <blockquote> set.delete (1); <br> console.log ([... set]) // должен возвращать [2, 3] <blockquote></blockquote></blockquote></p>
</section>

Remove items from a set in ES6

<section id="description">
<p>Давайте посмотрим на методы .has и .size, доступные на объекте Set ES6. Сначала создайте набор ES6 <code>var set = new Set([1,2,3]);</code> Метод .has проверяет, содержится ли это значение в наборе. <code>var hasTwo = set.has(2);</code> Метод .size возвращает целое число, представляющее размер Set <code>var howBig = set.size;</code></p>
</section>

Use .has and .size on an ES6 Set

<section id="description">
<p>Вы помните оператор распространения ES6 <code>...</code> ? <code>...</code> может принимать истребимые объекты в ES6 и превращать их в массивы. Давайте создадим Set и проверим функцию спреда. <blockquote> var set = new Set ([1,2,3]); <br> var setToArr = [... set] <br> console.log (setToArr) // возвращает [1, 2, 3] </blockquote></p>
</section>

Use Spread and Notes for ES5 Set() Integration

<section id="description">
<p>В этом вызове вы создадите очередь приоритетов. Приоритетная очередь - это особый тип очереди, в которой элементы могут иметь дополнительную информацию, которая определяет их приоритет. Это может быть просто представлено целым числом. Приоритет элемента переопределяет порядок размещения при определении элементов последовательности. Если элемент с более высоким приоритетом помещается в очередь после элементов с более низким приоритетом, элемент с более высоким приоритетом будет удален до всех остальных. Например, предположим, что у нас есть очередь приоритетов с тремя элементами: <code>[['kitten', 2], ['dog', 2], ['rabbit', 2]]</code> Здесь второе значение (целое число) представляет приоритет элемента , Если мы ставим в очередь <code>['human', 1]</code> с приоритетом <code>1</code> (при условии, что более низкие приоритеты заданы приоритетом), тогда это будет первый элемент, который будет удален. Коллекция понравится: <code>[['human', 1], ['kitten', 2], ['dog', 2], ['rabbit', 2]]</code> . Мы начали писать <code>PriorityQueue</code> в редакторе кода. Вам нужно будет добавить метод <code>enqueue</code> для добавления элементов с приоритетом, метод <code>dequeue</code> для удаления элементов, метод <code>size</code> для возврата количества элементов в очереди, <code>front</code> метод для возврата элемента в передней части очереди и наконец, метод <code>isEmpty</code> , который вернет <code>true</code> если очередь пуста или <code>false</code> если это не так. <code>enqueue</code> должна принимать элементы с форматом, указанным выше ( <code>['human', 1]</code> ), где <code>1</code> представляет приоритет. <code>dequeue</code> должен возвращать только текущий элемент, а не его приоритет.</p></section>

Create a Priority Queue Class

<section id="description">
<p>В этом вызове вы создадите круговую очередность. Круговая очередь - это в основном очередь, которая записывает в конец коллекции, а затем начинает записывать себя в начале коллекции. Это тип структуры данных имеет некоторые полезные приложения в определенных ситуациях. Например, круговая очередь может использоваться для потоковой передачи. Как только очередь заполнена, новые мультимедийные данные просто начинают перезаписывать старые данные. Хорошим способом проиллюстрировать эту концепцию является массив: <blockquote> [1, 2, 3, 4, 5] <br> ^ Читать @ 0 <br> ^ Написать @ 0 </blockquote> Здесь чтение и запись находятся в положении <code>0</code> . Теперь очередь получает 3 новые записи <code>a</code> , <code>b</code> и <code>c</code> . Теперь наша очередь выглядит так: <blockquote> [a, b, c, 4, 5] <br> ^ Читать @ 0 <br> ^ Написать @ 3 </blockquote> Как читает читатель, он может удалить значения или сохранить их: <blockquote> [null, null, null, 4, 5] <br> ^ Читать @ 3 <br> ^ Написать @ 3 </blockquote> Когда запись достигает конца массива, он возвращается к началу: <blockquote> [f, null, null, d, e] <br> ^ Читать @ 3 <br> ^ Пишите @ 1 </blockquote> Этот подход требует постоянного объема памяти, но позволяет обрабатывать файлы большего размера. Инструкции: В этой задаче мы реализуем круговую очередь. Круговая очередь должна обеспечивать <code>enqueue</code> и <code>dequeue</code> методы , которые позволяют считывать и записывать данные в очередь. Сам класс должен также принять целое число, которое вы можете использовать, чтобы указать размер очереди при ее создании. Мы написали стартовую версию этого класса для вас в редакторе кода. Когда вы ставите объекты в очередь, указатель записи должен продвигаться вперед и возвращаться к началу, как только он достигнет конца очереди. Аналогично, указатель чтения должен продвигаться вперед при удалении элементов. Указателю записи не следует пропускать указатель чтения (наш класс не позволит вам перезаписывать данные, которые вы еще не читали), и указатель чтения не должен продвигать прошлые данные, которые вы написали. Кроме того, метод <code>enqueue</code> должен возвращать элемент, который вы указали, если он успешно и в противном случае возвращает <code>null</code> . Аналогичным образом, когда вы удаляете элемент, он должен быть возвращен, и если вы не можете удалить из очереди, вы должны вернуть <code>null</code> .</p></section>

Create a Circular Queue

<section id="description">
<p>Графы могут быть представлены по-разному. Здесь мы описываем один способ, который называется <dfn>списком смежности</dfn> . Список смежности по существу представляет собой маркированный список, в котором левой стороной является узел, а правая сторона - список всех других узлов, к которым он подключен. Ниже приведен список смежности. <blockquote> Node1: Node2, Node3 <br> Node2: Node1 <br> Node3: Node1 </blockquote> Выше - неориентированный граф, потому что <code>Node1</code> подключен к <code>Node2</code> и <code>Node3</code> , и эта информация соответствует соединениям <code>Node2</code> и <code>Node3</code> . Список смежности для ориентированного графа будет означать, что каждая строка списка показывает направление. Если выше было указано, то <code>Node2: Node1</code> будет означать, что направленный край указывает от <code>Node2</code> на <code>Node1</code> . Мы можем представить неориентированный граф выше как список смежности, помещая его в объект JavaScript. <blockquote> var undirectedG = { <br> Node1: ["Node2", "Node3"], <br> Node2: ["Node1"], <br> Node3: ["Node1"] <br> }; </blockquote> Это также можно более просто представить в виде массива, где узлы имеют только цифры, а не строковые метки. <blockquote> var unirectedGArr = [ <br> [1, 2], # Node1 <br> [0], # Node2 <br> [0] # Node3 <br> ]; </blockquote></p>
</section>

Adjacency List

<section id="description">
<p>Другим способом представления графика является его размещение в <dfn>матрице смежности</dfn> . Матрица <dfn>смежности</dfn> представляет собой двумерный (2D) массив, где каждый вложенный массив имеет такое же количество элементов, что и внешний массив. Другими словами, это матрица или сетка чисел, где числа представляют собой ребра. Нули означают, что нет границ или отношений. <blockquote> 1 2 3 <br> ------ <br> 1 | 0 1 1 <br> 2 | 1 0 0 <br> 3 | 1 0 0 </blockquote> Выше - очень простой, неориентированный граф, где у вас есть три узла, где первый узел подключен ко второму и третьему узлам. <strong>Примечание</strong> . Числа в верхней и левой частях матрицы являются только метками для узлов. Ниже приведена реализация JavaScript того же самого. <blockquote> var adjMat = [ <br> [0, 1, 1], <br> [1, 0, 0], <br> [1, 0, 0] <br> ]; </blockquote> В отличие от списка смежности, каждая «строка» матрицы должна иметь такое же количество элементов, что и узлы в графике. Здесь у нас есть три-три матрицы, что означает, что мы имеем три узла в нашем графике. Ориентированный граф будет похож. Ниже приведен график, в котором первый узел имеет ребро, указывающее на второй узел, а затем второй узел имеет ребро, указывающее на третий узел. <blockquote> var adjMatDirected = [ <br> [0, 1, 0], <br> [0, 0, 1], <br> [0, 0, 0] <br> ]; </blockquote> Графики также могут иметь <dfn>веса</dfn> по краям. До сих пор у нас есть <dfn>невзвешенные</dfn> края, где только наличие и отсутствие ребра двоично ( <code>0</code> или <code>1</code> ). Вы можете иметь разные веса в зависимости от вашего приложения.</p></section>

Adjacency Matrix

<section id="description">
<p>Еще один способ представить график - положить его в <dfn>матрицу инцидентности.</dfn> Матрица <dfn>инцидентности</dfn> представляет собой двумерный (2D) массив. Вообще говоря, матрица инцидентов связывает два разных класса объектов между двумя его измерениями. Такая матрица подобна матрице смежности. Тем не менее, строки и столбцы означают что-то еще здесь. В графах мы имеем ребра и узлы. Это будут наши «два разных класса объектов». Эта матрица будет содержать строки, в которых узлы и столбцы будут ребрами. Это означает, что мы можем иметь нечетное количество строк и столбцов. Каждый столбец будет представлять собой уникальный ребро. Кроме того, каждое ребро соединяет два узла. Чтобы показать, что существует ребро между двумя узлами, вы поместите 1 в две строки определенного столбца. Ниже приведен граф из 3 узлов с одним ребром между узлом 1 и узлом 3. <blockquote> 1 <br> --- <br> 1 | 1 <br> 2 | 0 <br> 3 | 1 </blockquote> Ниже приведен пример <code>incidence matrix</code> с 4 ребрами и 4 узлами. Помните, что столбцы - это ребра, а строки - сами узлы. <blockquote> 1 2 3 4 <br> -------- <br> 1 | 0 1 1 1 <br> 2 | 1 1 0 0 <br> 3 | 1 0 0 1 <br> 4 | 0 0 1 0 </blockquote> Ниже приведена реализация JavaScript того же самого. <blockquote> var incMat = [ <br> [0, 1, 1, 1], <br> [1, 1, 0, 0], <br> [1, 0, 0, 1], <br> [0, 0, 1, 0] <br> ]; </blockquote> Чтобы создать ориентированный граф, используйте <code>-1</code> для края, оставляющего определенный узел, и <code>1</code> для края, входящего в узел. <blockquote> var incMatDirected = [ <br> [0, -1, 1, -1], <br> [-1, 1, 0, 0], <br> [1, 0, 0, 1], <br> [0, 0, -1, 0] <br> ]; </blockquote> Графики также могут иметь <dfn>веса</dfn> по краям. До сих пор у нас есть <dfn>невзвешенные</dfn> края, где только наличие и отсутствие ребра двоично ( <code>0</code> или <code>1</code> ). Вы можете иметь разные веса в зависимости от вашего приложения. Другой вес представлен как числа больше 1.</p></section>

Incidence Matrix

<section id="description">
<p>Эта серия проблем приведет к созданию структуры данных дерева. Деревья - важная и универсальная структура данных в информатике. Конечно, их имя исходит из того факта, что при визуализации они очень похожи на деревья, с которыми мы знакомы в естественном мире. Структура данных дерева начинается с одного узла, обычно называемого корнем, и отсюда разветвляется на дополнительные узлы, каждый из которых может иметь больше дочерних узлов и т. Д. И т. Д. Структура данных обычно визуализируется с корневым узлом вверху; вы можете думать об этом, как естественное дерево перевернулось вверх дном. Сначала давайте опишем некоторую общую терминологию, с которой мы столкнемся с деревьями. Корневой узел - это вершина дерева. Точки данных в дереве называются узлами. Узлы с ветвями, ведущими к другим узлам, называются родителями узла, к которому ведет ветвь (дочерний элемент). Другие более сложные семейные термины применяются, как и следовало ожидать. Поддерево относится ко всем потомкам конкретного узла, ветви могут упоминаться как ребра, а листовые узлы - узлы в конце дерева, у которых нет детей. Наконец, обратите внимание, что деревья являются по своей природе рекурсивными структурами данных. То есть, любые дочерние узлы являются родителями собственного поддерева и так далее. Рекурсивный характер деревьев важен для понимания при разработке алгоритмов для общих операций дерева. Для начала обсудим конкретный тип дерева - двоичное дерево. Фактически, мы фактически обсудим конкретное двоичное дерево, двоичное дерево поиска. Давайте опишем, что это значит. Хотя структура данных дерева может иметь любое количество ветвей в одном узле, двоичное дерево может иметь только две ветви для каждого узла. Кроме того, двоичное дерево поиска упорядочено относительно дочерних поддеревьев, так что значение каждого узла в левом поддереве меньше или равно значению родительского узла, а значение каждого узла в правом поддереве равно больше или равно значению родительского узла. Очень полезно визуализировать эти отношения, чтобы лучше понять это: <div style="width: 100%; display: flex; justify-content: center; align-items: center;"><img style="width: 100%; max-width: 350px;" src="https://user-images.githubusercontent.com/18563015/32136009-1e665d98-bbd6-11e7-9133-63184f9f9182.png"></div> Теперь это упорядоченное отношение очень легко увидеть. Обратите внимание, что каждое значение слева от корневого узла 8 меньше 8, а каждое значение справа больше 8. Также обратите внимание, что это отношение относится и к каждому из поддеревьев. Например, первый левый дочерний элемент является поддеревом. 3 является родительским узлом и имеет ровно два дочерних узла - по правилам, определяющим деревья двоичного поиска, мы знаем, даже не глядя, что левый ребенок этого узла (и любого его дочернего элемента) будет меньше 3, а правый child (и любой из его дочерних элементов) будет больше 3 (но также меньше корневого значения структуры) и т. д. Двоичные деревья поиска - очень распространенные и полезные структуры данных, поскольку они обеспечивают логарифмическое время в среднем случае для нескольких общих операций, таких как поиск, вставка и удаление. Инструкции: Мы начнем просто. Мы определили скелет структуры двоичного дерева поиска здесь в дополнение к функции для создания узлов для нашего дерева. Обратите внимание, что каждый узел может иметь левое и правое значение. Они будут назначены дочерние поддеревья, если они существуют. В нашем двоичном дереве поиска определите два метода: <code>findMin</code> и <code>findMax</code> . Эти методы должны возвращать минимальное и максимальное значение, хранящиеся в двоичном дереве поиска (не беспокойтесь о добавлении значений в дерево на данный момент, мы добавили некоторые в фоновом режиме). Если вы застряли, подумайте об инварианте, который должен быть истинным для двоичных деревьев поиска: каждое левое поддерево меньше или равно его родительскому элементу, и каждое правое поддерево больше или равно его родительскому. Давайте также скажем, что наше дерево может хранить только целочисленные значения. Если дерево пустое, любой метод должен возвращать значение <code>null</code> .</p></section>

Find the Minimum and Maximum Value in a Binary Search Tree

<section id="description">
<p>Теперь, когда у нас есть идея об основах, давайте напишем более сложный метод. В этой задаче мы создадим метод добавления новых значений в наше дерево двоичного поиска. Метод следует называть <code>add</code> и он должен принимать целочисленное значение для добавления в дерево. Позаботьтесь о сохранении инварианта двоичного дерева поиска: значение в каждом левом ребне должно быть меньше или равно родительскому значению, а значение в каждом правом дочернем случае должно быть больше или равно родительскому значению. Здесь давайте сделаем так, чтобы наше дерево не могло хранить повторяющиеся значения. Если мы попытаемся добавить значение, которое уже существует, метод должен вернуть значение <code>null</code> . В противном случае, если добавление будет успешным, <code>undefined</code> должен быть возвращен. Подсказка: деревья - это, естественно, рекурсивные структуры данных!</p></section>

Add a New Element to a Binary Search Tree

<section id="description">
<p>Теперь, когда у нас есть общее представление о том, какое бинарное дерево поиска давайте поговорим об этом чуть подробнее. Двоичные деревья поиска предоставляют логарифмическое время для общих операций поиска, вставки и удаления в среднем случае и линейного времени в худшем случае. Почему так? Каждая из этих основных операций требует от нас найти элемент в дереве (или в случае вставки, чтобы найти, куда он должен идти), и из-за древовидной структуры каждого родительского узла мы разветвляемся влево или вправо и фактически исключаем половину размера оставшегося дерева. Это делает поиск пропорциональным логарифму числа узлов в дереве, что создает логарифмическое время для этих операций в среднем случае. Хорошо, но как насчет худшего случая? Ну, подумайте о построении дерева из следующих значений, добавив их слева направо: <code>10</code> , <code>12</code> , <code>17</code> , <code>25</code> . Следуя нашим правилам для двоичного дерева поиска, мы добавим <code>12</code> справа от <code>10</code> , <code>17</code> справа от него и <code>25</code> справа от него. Теперь наше дерево напоминает связанный список и, пройдя его, чтобы найти <code>25</code> , потребовало бы, чтобы мы проходили все элементы линейным способом. Следовательно, линейное время в худшем случае. Проблема здесь в том, что дерево неуравновешено. Мы рассмотрим немного больше, что это означает в следующих задачах. Инструкции: В этой задаче мы создадим утилиту для нашего дерева. Напишите метод <code>isPresent</code> который принимает целочисленное значение в качестве входных данных и возвращает логическое значение для наличия или отсутствия этого значения в двоичном дереве поиска.</p></section>

Check if an Element is Present in a Binary Search Tree

<section id="description">
<p>В последнем вызове мы описали сценарий, в котором дерево может стать неуравновешенным. Чтобы понять концепцию баланса, давайте посмотрим на другое свойство дерева: height. Высота в дереве представляет собой расстояние от корневого узла до любого заданного листового узла. Различные пути в сильно разветвленной структуре дерева могут иметь разную высоту, но для данного дерева будет минимальная и максимальная высота. Если дерево сбалансировано, эти значения будут отличаться не более чем на один. Это означает, что в сбалансированном дереве все листовые узлы существуют на одном уровне, или если они не находятся на одном уровне, они не более одного уровня друг от друга. Свойство баланса важно для деревьев, потому что именно это определяет эффективность древовидных операций. Как мы объяснили в последнем задаче, мы сталкиваемся с худшей временной сложностью для сильно неуравновешенных деревьев. Самобалансирующиеся деревья обычно используются для учета этой проблемы в деревьях с динамическими наборами данных. К общим примерам относятся деревья AVL, красно-черные деревья и B-деревья. Эти деревья содержат дополнительную внутреннюю логику, которая перебалансирует дерево, когда вставки или удаления создают состояние дисбаланса. Примечание. Аналогичным свойством высоты является глубина, которая относится к тому, насколько далеко данный узел находится от корневого узла. Инструкции: Напишите два метода для нашего двоичного дерева: <code>findMinHeight</code> и <code>findMaxHeight</code> . Эти методы должны возвращать целочисленное значение для минимальной и максимальной высоты в заданном двоичном дереве, соответственно. Если узел пуст, назначим ему высоту <code>-1</code> (это базовый случай). Наконец, добавьте третий метод <code>isBalanced</code> который возвращает <code>true</code> или <code>false</code> зависимости от того, сбалансировано ли дерево или нет. Вы можете использовать первые два метода, которые вы только что написали, чтобы определить это.</p></section>

Find the Minimum and Maximum Height of a Binary Search Tree

<section id="description">
<p>Мы знаем, как искать двоичное дерево поиска для определенного значения. Но что, если мы просто хотим исследовать все дерево? Или что, если у нас нет упорядоченного дерева, и нам нужно просто искать значение? Здесь мы представим некоторые методы обхода дерева, которые можно использовать для изучения структур древовидных данных. Сначала - поиск по глубине. При поиске по глубине, заданное поддерево рассматривается как можно глубже, прежде чем поиск продолжит переход к другому поддереву. Это можно сделать тремя способами: In-order: Начать поиск на самом левом узле и завершить на самом правом узле. Предварительный порядок: исследуйте все корни перед листьями. Post-order: Исследуйте все листья перед корнями. Как вы можете догадаться, вы можете выбрать различные методы поиска в зависимости от того, какие данные хранят ваше дерево и что вы ищете. Для двоичного дерева поиска обход ордера возвращает узлы в отсортированном порядке. Инструкции: Здесь мы создадим эти три метода поиска в нашем двоичном дереве поиска. Поиск по глубине - это неотъемлемая рекурсивная операция, которая продолжает исследовать дальнейшие поддеревья, пока присутствуют дочерние узлы. Как только вы поймете эту базовую концепцию, вы можете просто изменить порядок, в котором вы исследуете узлы и поддеревья, чтобы произвести любой из трех поисков выше. Например, в post-order search мы хотели бы перечислить весь путь до листового узла, прежде чем мы начнем возвращать любой из самих узлов, тогда как в предварительном поиске мы хотели бы сначала вернуть узлы, а затем продолжить рекурсию вниз по дереву. Определение <code>inorder</code> , <code>preorder</code> , и <code>postorder</code> метода на нашем дереве. Каждый из этих методов должен возвращать массив элементов, которые представляют обход дерева. Обязательно верните целые значения в каждом узле массива, а не сами узлы. Наконец, возвращаем значение <code>null</code> если дерево пусто.</p></section>

Use Depth First Search in a Binary Search Tree

<section id="description">
<p>Здесь мы представим другой метод обхода дерева: поиск по ширине. В отличие от методов поиска по глубине из последней задачи, поиск по ширине исследует все узлы на заданном уровне внутри дерева, а затем переходит на следующий уровень. Как правило, очереди используются в качестве вспомогательных структур данных при разработке алгоритмов поиска по ширине. В этом методе мы начинаем с добавления корневого узла в очередь. Затем мы начинаем цикл, в котором мы деактивируем первый элемент в очереди, добавим его в новый массив и затем проверим оба его дочерних поддерева. Если его дочерние элементы не равны нулю, все они помещаются в очередь. Этот процесс продолжается до тех пор, пока очередь не будет пустой. Инструкции. Давайте создадим метод поиска ширины в нашем дереве, называемый <code>levelOrder</code> . Этот метод должен возвращать массив, содержащий значения всех узлов дерева, исследованных в широком смысле. Обязательно верните значения в массиве, а не сами узлы. Уровень должен пересекаться слева направо. Далее, давайте напишем аналогичный метод <code>reverseLevelOrder</code> который выполняет тот же поиск, но в обратном направлении (справа налево) на каждом уровне.</p></section>

Use Breadth First Search in a Binary Search Tree

<section id="description">
<p>Это первая из трех задач, когда мы будем выполнять более сложную операцию в двоичных деревьях поиска: удаление. Удаление затруднено, поскольку удаление узлов ломает ссылки в дереве. Эти ссылки должны быть тщательно восстановлены для обеспечения сохранения структуры двоичного дерева. Для некоторых исключений это означает, что дерево должно быть перестроено. В общем случае вы столкнетесь с одним из трех случаев, когда пытаетесь удалить узел: Leaf Node: цель для удаления имеет ноль детей. Один ребенок: у цели для удаления только один ребенок. Двое детей: цель для удаления имеет два дочерних узла. Удаление листового узла легко, мы просто удалим его. Удаление узла одним ребенком также относительно просто, мы просто удалим его и связаем его родительский с дочерним узлом удаляемого узла. Однако удалить узел с двумя детьми сложнее, поскольку это создает два дочерних узла, которые необходимо переподключить к родительскому дереву. Мы посмотрим, как справиться с этим делом в третьем вызове. Кроме того, вы должны помнить о некоторых случаях при обработке удаления. Что делать, если дерево пустое? Что делать, если удаляемый узел является корневым узлом? Что делать, если в дереве есть только два элемента? Теперь давайте рассмотрим первый случай, когда мы удаляем листовой узел. Инструкции: Создайте метод на нашем двоичном дереве, который называется <code>remove</code> . Здесь мы построим логику для операции удаления. Во-первых, вам нужно создать функцию в удалении, которая находит узел, который мы пытаемся удалить в текущем дереве. Если узел отсутствует в дереве, <code>remove</code> должен вернуть значение <code>null</code> . Теперь, если целевой узел является листовым узлом без детей, то родительская ссылка на него должна быть установлена ​​в <code>null</code> . Это эффективно удаляет узел из дерева. Для этого вам нужно будет отслеживать родительский узел узла, который мы также пытаемся удалить. Также будет полезно создать способ отслеживания числа дочерних узлов целевого узла, так как это определит, к какому случаю относится наше удаление. Мы рассмотрим второй и третий случаи в следующих задачах. Удачи!</p></section>

Delete a Leaf Node in a Binary Search Tree

<section id="description">
<p>Now that we can delete leaf nodes let's move on to the second case: deleting a node with one child. For this case, say we have a tree with the following nodes 1 — 2 — 3 where 1 is the root. To delete 2, we simply need to make the right reference in 1 point to 3. More generally to delete a node with only one child, we make that node's parent reference the next node in the tree.</p></section>

Delete a Node with One Child in a Binary Search Tree

<section id="description">
<p>Удаление узлов, имеющих двух детей, является самым сложным для реализации. Удаление такого узла приводит к двум поддеревьям, которые больше не связаны с исходной древовидной структурой. Как мы можем их восстановить? Один из методов заключается в том, чтобы найти наименьшее значение в правом поддереве целевого узла и заменить целевой узел на это значение. Выбор замены таким образом гарантирует, что он больше, чем каждый узел в левом поддереве, он становится новым родителем, но также меньше, чем каждый узел в правом поддереве, он становится новым родителем. После этой замены узел замены должен быть удален из правого поддерева. Даже эта операция сложна, потому что замена может быть листом, или она сама может быть родителем правильного поддерева. Если это лист, мы должны удалить ссылку на родителя. В противном случае это должен быть правильный ребенок цели. В этом случае мы должны заменить целевое значение значением замены и сделать целевую ссылку правильным ребенком замены. Инструкции: Закончим наш метод <code>remove</code> , обработав третий случай. Мы снова предоставили код для первых двух случаев. Добавьте код для обработки целевых узлов двумя детьми. Любые случаи краев, о которых нужно знать? Что, если дерево имеет только три узла? По завершении этого будет завершена операция удаления двоичных деревьев поиска. Хорошая работа, это довольно сложная проблема!</p></section>

Delete a Node with Two Children in a Binary Search Tree

<section id="description">
<p>Здесь мы создадим функцию инвертирования двоичного дерева. Учитывая двоичное дерево, мы хотим создать новое дерево, эквивалентное зеркальному изображению этого дерева. Выполнение обхода порядка на инвертированном дереве будет исследовать узлы в обратном порядке по сравнению с обходным порядком исходного дерева. Напишите метод для этого, который называется <code>invert</code> на нашем двоичном дереве. Вызов этого метода должен инвертировать текущую древовидную структуру. В идеале мы хотели бы сделать это на месте в линейном времени. То есть мы только посещаем каждый узел один раз, и мы изменяем существующую древовидную структуру, когда мы идем, без использования дополнительной памяти. Удачи!</p></section>

Invert a Binary Tree

<section id="description">
<p>Здесь мы перейдем от двоичных деревьев поиска и рассмотрим другой тип древовидной структуры, называемый trie. Trie - это упорядоченное дерево поиска, обычно используемое для хранения строк или более общих ассоциативных массивов или динамических наборов данных, в которых ключи являются строками. Они очень хороши в хранении наборов данных, когда многие ключи имеют перекрывающиеся префиксы, например, все слова в словаре. В отличие от двоичного дерева, узлы не связаны с фактическими значениями. Вместо этого путь к узлу представляет собой конкретный ключ. Например, если бы мы хотели сохранить строковый код в trie, у нас было бы четыре узла, по одному для каждой буквы: c - o - d - e. После этого пути через все эти узлы затем создадут код как строку - этот путь является ключом, который мы сохранили. Затем, если бы мы хотели добавить строковое кодирование, он разделил бы первые три узла кода, прежде чем разветвиться после d. Таким образом, большие наборы данных могут храниться очень компактно. Кроме того, поиск может быть очень быстрым, поскольку он фактически ограничен длиной строки, которую вы храните. Кроме того, в отличие от двоичных деревьев узел может хранить любое количество дочерних узлов. Как вы могли догадаться из приведенного выше примера, некоторые метаданные обычно хранятся в узлах, которые содержат конец ключа, так что на последующих обходах этот ключ все еще может быть восстановлен. Например, если мы добавили коды в наш пример выше, нам понадобится некоторый способ узнать, что e в коде представляет собой конец ключа, который был ранее введен. В противном случае эта информация будет эффективно потеряна при добавлении кодов. Инструкции: создадим три для хранения слов. Он будет принимать слова через метод добавления и хранить их в структуре данных trie. Это также позволит нам запросить, является ли данная строка словом с методом isWord и извлекает все слова, введенные в trie с помощью метода печати. isWord должен возвращать логическое значение, и print должен возвращать массив всех этих слов в виде строковых значений. Чтобы мы убедились, что эта структура данных реализована правильно, мы предоставили структуру узла для каждого узла в дереве. Каждый узел будет объектом с свойством keys, являющимся объектом JavaScript Map. Это будет содержать отдельные буквы, которые являются действительными ключами каждого узла. Мы также создали свойство конца на узлах, которое может быть установлено в true, если узел представляет собой завершение слова.</p></section>

Create a Trie Search Tree

<section id="description">
<p>Все связанные списки, которые мы создали до сих пор, представляют собой отдельные списки. Здесь мы создадим <dfn>двусвязный список</dfn> . Как следует из названия, узлы в двусвязном списке имеют ссылки на следующий и предыдущий узел в списке. Это позволяет нам перемещаться по списку в обоих направлениях, но для этого требуется больше памяти, потому что каждый узел должен содержать дополнительную ссылку на предыдущий узел в списке.</p></section>

Create a Doubly Linked List

<section id="description">
<p>Давайте создадим еще один метод для нашего дважды связанного списка, который называется reverse, который меняет список на месте. Как только метод выполняется, голова должна указывать на предыдущий хвост, а хвост должен указывать на предыдущую голову. Теперь, если мы пересекаем список от головы до хвоста, мы должны встретить узлы в обратном порядке по сравнению с исходным списком. Попытка изменить пустой список должна вернуть значение null.</p></section>

Reverse a Doubly Linked List

<section id="description">
<p>Теперь мы перейдем к другой структуре данных дерева, двоичной куче. Бинарная куча - частично упорядоченное двоичное дерево, которое удовлетворяет свойству кучи. Свойство heap указывает связь между родительским и дочерним узлами. У вас может быть максимальная куча, в которой все родительские узлы больше или равны их дочерним узлам или минимальная куча, в которой верно обратное. Двоичные кучи также являются полными бинарными деревьями. Это означает, что все уровни дерева полностью заполнены, и если последний уровень частично заполнен, он заполняется слева направо. Хотя двоичные кучи могут быть реализованы как древовидные структуры с узлами, которые содержат левую и правую ссылки, частичный порядок в соответствии с свойством кучи позволяет нам представлять кучу с массивом. Отношения родитель-дети - это то, что нас интересует, и с простой арифметикой мы можем вычислить дочерние элементы любого родителя и родителя любого дочернего узла. Например, рассмотрим это представление массива двоичной мини-кучи: <code>[ 6, 22, 30, 37, 63, 48, 42, 76 ]</code> Корневой узел - это первый элемент, 6. Его дети - 22 и 30. Если мы посмотрим при взаимосвязи между индексами массива этих значений для индекса i дети равны 2 * i + 1 и 2 * i + 2. Аналогично, элемент с индексом 0 является родителем этих двух детей по индексам 1 и 2. Подробнее Как правило, мы можем найти родительский узел узла в любом индексе со следующим: (i - 1) / 2. Эти шаблоны будут выполняться, поскольку бинарное дерево растет до любого размера. Наконец, мы можем сделать небольшую корректировку, чтобы сделать эту арифметику еще проще, пропустив первый элемент в массиве. Для этого создается следующее отношение для любого элемента в указанном индексе i: Пример Array: <code>[ null, 6, 22, 30, 37, 63, 48, 42, 76 ]</code> Левый дочерний элемент: i * 2 Правильный дочерний элемент : i * 2 + 1 Родитель элемента: i / 2 После того, как вы обернете свою голову вокруг математики, использование представления массива очень полезно, потому что расположение узлов можно быстро определить с помощью этой арифметики, а использование памяти уменьшилось, потому что вам не нужно для поддержки ссылок на дочерние узлы. Инструкции: Здесь мы создадим максимальную кучу. Начните с создания метода insert, который добавляет элементы в нашу кучу. При вставке важно всегда сохранять свойство кучи. Для максимальной кучи это означает, что корневой элемент всегда должен иметь наибольшее значение в дереве, а все родительские узлы должны быть больше, чем их дети. Для реализации массива кучи это правило выполняется в три этапа: добавьте новый элемент в конец массива. Если элемент больше, чем его родители, переключите их. Продолжайте переключение до тех пор, пока новый элемент не станет меньше его родителя или вы не достигнете корня дерева. Наконец, добавьте метод печати, который возвращает массив всех элементов, которые были добавлены в кучу.</p></section>

Insert an Element into a Max Heap

<section id="description">
<p>Теперь, когда мы можем добавить элементы в нашу кучу, посмотрим, как мы можем удалить элементы. Для снятия и вставки элементов требуется аналогичная логика. В максимальной куче вы обычно хотите удалить наибольшую ценность, поэтому это требует просто извлечь ее из корня нашего дерева. Это разрушит свойство кучи нашего дерева, поэтому мы должны каким-то образом восстановить его. Как правило, для максимальной кучи это делается следующим образом: переместите последний элемент в куче в корневую позицию. Если любой корень корня больше, чем он, замените корень с дочерним значением большего значения. Продолжайте замену, пока родитель больше, чем оба ребенка, или вы достигнете последнего уровня в дереве. Инструкции: добавьте метод в нашу максимальную кучу, называемую remove. Этот метод должен вернуть наибольшее значение, которое было добавлено в нашу максимальную кучу и удалить его из кучи. Он также должен изменить порядок кучи, чтобы сохранить свойство кучи. После удаления элемента следующий главный элемент, оставшийся в куче, должен стать корнем. Здесь также добавьте свой метод вставки.</p></section>

Remove an Element from a Max Heap

<section id="description">
<p>Теперь, когда мы можем добавлять и удалять элементы, давайте посмотрим, как можно использовать некоторые кучи приложений. Кучи обычно используются для реализации очередей приоритетов, поскольку они всегда хранят элемент наибольшего или наименьшего значения в первой позиции. Кроме того, они используются для реализации алгоритма сортировки, называемого сортировкой кучи. Посмотрим, как это сделать. Сортировка кучи использует минимальную кучу, обратную к максимальной куче. Минимальная куча всегда сохраняет элемент наименьшего значения в корневой позиции. Heap sort работает, беря несортированный массив, добавляя каждый элемент в массив в кучу минут, а затем извлекает каждый элемент из кучи min в новый массив. Структура минимальной кучи гарантирует, что новый массив будет содержать исходные элементы по крайней мере до наибольшего порядка. Это один из наиболее эффективных алгоритмов сортировки со средней и наихудшей производительностью O (nlog (n)). Инструкции: Давайте реализуем кучу сортировки с минимальной кучей. Не стесняйтесь адаптировать свой максимальный код кучи. Создайте объект MinHeap с помощью методов вставки, удаления и сортировки. Метод sort должен возвращать массив из всех элементов в куче минимальной сортировки от минимального до самого большого.</p></section>

Implement Heap Sort with a Min Heap

<section id="description">
<p>The new version of JavaScript provides us with a built-in Map object which provides much of the functionality we wrote by hand in the last challenge. This Map object, although similar to regular JavaScript objects, provides some useful functionality that normal objects lack. For example, an ES6 Map tracks the insertion order of items that are added to it. Here is a more complete overview of its methods:</p><p><code>.has(key)</code> returns true or false based on the presence of a key</p><p><code>.get(key)</code> returns the value associated with a key</p><p><code>.set(key, value)</code> sets a new key, value pair</p><p><code>.delete(key)</code> removes a key, value pair</p><p><code>.clear()</code> removes all key, value pairs</p><p><code>.entries()</code> returns an array of all the keys in insertion order</p><p><code>.values()</code> returns an array of all the values in insertion order</p></section>

Create an ES6 JavaScript Map

<section id="description">
<p>В этой задаче мы узнаем о хэш-таблицах. Хэш-таблица используется для реализации ассоциативных массивов или сопоставлений пар ключ-значение, таких как объекты и Карты, которые мы только что изучали. Например, объект JavaScript может быть реализован как хэш-таблица (его фактическая реализация будет зависеть от среды, в которой он работает). Способ работы хеш-таблицы состоит в том, что он принимает ключевой ввод и делит этот ключ на некоторое числовое значение. Это числовое значение затем используется как фактический ключ, связанное значение сохраняется. Затем, если вы снова попытаетесь получить доступ к тому же ключу, хеширующая функция обработает ключ, вернет тот же числовой результат, который затем будет использоваться для поиска связанного значения. Это обеспечивает очень эффективное время поиска O (n) в среднем. Хэш-таблицы могут быть реализованы как массивы с хеш-функциями, производящими индексы массивов в заданном диапазоне. В этом методе выбор размера массива важен, как и функция хэширования. Например, что, если функция хэширования дает одно и то же значение для двух разных ключей? Это называется столкновением. Один из способов обработки коллизий - просто сохранить обе пары ключ-значение в этом индексе. Затем, после поиска либо, вам придется перебирать ведро предметов, чтобы найти ключ, который вы ищете. Хорошая функция хэширования минимизирует столкновения для поддержания эффективного времени поиска. Здесь мы не будем беспокоиться о деталях хэширования или реализации хеш-таблицы, мы просто попытаемся получить общее представление о том, как они работают. Инструкции: Давайте создадим базовую функциональность хеш-таблицы. Мы создали наивную функцию хэширования для вас. Вы можете передать строковое значение в хэш функции, и оно вернет хешированное значение, которое вы можете использовать в качестве ключа для хранения. Храните элементы на основе этого хешированного значения в объекте this.collection. Создайте эти три метода: добавьте, удалите и найдите. Первый должен принять пару значений ключа для добавления в хеш-таблицу. Второй должен удалить пару ключ-значение при передаче ключа. Третий должен принять ключ и вернуть связанное значение или null, если ключ отсутствует. Обязательно напишите свой код для учета конфликтов!</p></section>

Create a Hash Table

<section id="description">
<p>До сих пор мы изучили разные способы создания представлений графиков. Что теперь? Один естественный вопрос - какие расстояния между любыми двумя узлами графика? Введите <dfn>алгоритмы обхода графа</dfn> . <dfn>Алгоритмы</dfn> траверса - это алгоритмы для перемещения или посещения узлов в графе. Одним типом алгоритма обхода является алгоритм поиска ширины. Этот алгоритм начинается с одного узла, сначала посещает всех его соседей, которые находятся на одном крае, а затем переходит к каждому из своих соседей. Визуально это то, что делает алгоритм. <img class="img-responsive" src="https://camo.githubusercontent.com/2f57e6239884a1a03402912f13c49555dec76d06/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f342f34362f416e696d617465645f4246532e676966"> Чтобы реализовать этот алгоритм, вам нужно будет ввести структуру графика и узел, с которого вы хотите начать. Во-первых, вы хотите знать расстояния от стартового узла. Это вы хотите сначала начать все свои расстояния на некоторое количество, например <code>Infinity</code> . Это дает ссылку на случай, когда узел может быть недоступен из вашего стартового узла. Затем вы захотите перейти от стартового узла к своим соседям. Эти соседи находятся на одном крае, и в этот момент вы должны добавить одну единицу расстояния до расстояний, которые вы отслеживаете. Наконец, важной структурой данных, которая поможет реализовать алгоритм поиска по ширине, является очередь. Это массив, в котором вы можете добавлять элементы в один конец и удалять элементы с другого конца. Это также известно как структура данных <dfn>FIFO</dfn> или <dfn>First-In-First-Out</dfn> .</p></section>

Breadth-First Search

<section id="description">
<p>Подобно <dfn>поиску в ширину</dfn> , здесь мы узнаем о другом алгоритме обхода графа, называемом методом поиска в <dfn>глубину</dfn> . В то время как поиск по ширине ищет инкрементные длины кромок от исходного узла, <dfn>поиск по глубине сначала</dfn> идет по пути ребер, насколько это возможно. Как только он достигнет одного конца пути, поиск вернется к последнему узлу с не посещенным краем пути и продолжит поиск. Ниже приведена визуализация того, что делает алгоритм, когда верхний узел является отправной точкой поиска. <img class="img-responsive" src="https://camo.githubusercontent.com/aaad9e39961daf34d967c616edeb50abf3bf1235/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f372f37662f44657074682d46697273742d5365617263682e676966"> Простым выходом этого алгоритма является список узлов, которые достижимы с данного узла. Поэтому при реализации этого алгоритма вам нужно будет отслеживать узлы, которые вы посещаете.</p></section>

Depth-First Search

<section id="description">
<p>В следующих нескольких упражнениях мы собираемся создать функцию для эмуляции структуры данных, называемой «Set». Набор подобен массиву, но он не может содержать повторяющиеся значения. Типичное использование набора - это просто проверить наличие предмета. Это может быть реализовано с помощью объекта, например: <blockquote> var set = new Object (); <br> set.foo = true; <br> // Смотрите, существует ли foo в нашем наборе: <br> console.log (set.foo) // true </blockquote> В следующих нескольких упражнениях мы создадим полнофункциональный набор с нуля. Для этого упражнения создайте функцию, которая добавит значение в нашу коллекцию наборов, если это значение еще не существует в наборе. Например: <blockquote> this.add = function (element) { <br> // некоторый код для добавления значения к набору <br> } </blockquote> Функция должна возвращать значение <code>true</code> если значение успешно добавлено, а <code>false</code> противном случае.</p></section>

Create a Set Class

<section id="description">
<p>В этом упражнении мы собираемся создать функцию размера для нашего Set. Эта функция должна быть названа <code>this.size</code> и она должна вернуть размер коллекции.</p></section>

Size of the Set

<section id="description">
<p>Следующие несколько проблем будут охватывать карты и хеш-таблицы. Карты - это структуры данных, в которых хранятся пары ключ-значение. В JavaScript они доступны для нас как объекты. Карты обеспечивают быстрый поиск сохраненных элементов на основе значений ключей и являются очень распространенными и полезными структурами данных. Инструкции: Давайте попробуем создать собственную карту. Поскольку объекты JavaScript обеспечивают гораздо более эффективную структуру карты, чем все, что мы могли бы здесь написать, это в первую очередь предназначено для обучения. Однако объекты JavaScript предоставляют нам определенные операции. Что, если мы хотим определить пользовательские операции? Используйте объект <code>Map</code> указанный здесь как обертка вокруг <code>object</code> JavaScript. Создайте следующие методы и операции над объектом Map: <ul><li> <code>add</code> принимает пару <code>key, value</code> для добавления на карту. </li><li> <code>remove</code> принимает ключ и удаляет связанную пару <code>key, value</code> </li><li> <code>get</code> принимает <code>key</code> и возвращает сохраненное <code>value</code> </li><li> <code>has</code> принимает <code>key</code> и возвращает <dfn>истину</dfn> , если ключ существует , или <dfn>ложь</dfn> , если она не делает. </li><li> <code>values</code> возвращают массив всех значений на карте </li><li> <code>size</code> возвращает количество элементов на карте </li><li> <code>clear</code> пустую карту </li></ul></p>
</section>