Привет, друзья!
В этой серии статей мы продолжаем разбирать структуры данных и алгоритмы, представленные в этом замечательном репозитории. Это вторая часть серии.
Сегодня мы будем говорить о таких структурах данных, как хэш-таблица, куча, очередь с приоритетом и префиксное дерево.
Код, представленный в этой и других статьях серии, можно найти в этом репозитории.
Интересно? Тогда прошу под кат.
5. Хэш-таблица
Описание
Хэш-таблица (hash table) — это структура данных, которая реализует абстрактный тип данных "ассоциативный массив" и позволяет хранить пары "ключ-значение". Хэш-таблица использует так называемую хэш-функцию (hash function), которая принимает ключ и возвращает индекс массива, по которому будет храниться значение (см. хорошее видео про хэширование). Пример хэш-таблицы, в которой ключом выступает имя человека, а значением адрес его электронной почты:
В идеале хэш-функция должна генерировать уникальный индекс для каждого ключа. Однако реальные хэш-таблицы используют несовершенные хэш-функции, генерирующие одинаковые индексы для разных ключей. Такие ситуации называются коллизиями (collisions). Существует несколько способов их решения, наиболее популярными из которых являются: хэш-таблица с цепочками и хэш-таблица с открытой адресацией.
Метод цепочек подразумевает хранение значений, соответствующих одному индексу в виде связного списка (linked list) (см. часть 1, раздел 1):
Метод открытой адресации помещает значение по совпадающему индексу в первую свободную ячейку:
Реализация
Приступаем к реализации хэш-таблицы:
// data-structures/hash-table.js
// Импортируем конструктор связного списка
// (мы будем использовать метод цепочек для разрешения коллизий)
import LinkedList from './linked-list'
// Дефолтный размер таблицы
// (в реальности размер будет намного больше)
const defaultHashTableSize = 32
// Хэш-таблица
export default class HashTable {
constructor(size = defaultHashTableSize) {
// Создаем таблицу указанного размера и
// заполняем ее пустыми связными списками
this.buckets = new Array(size).fill(null).map(() => new LinkedList())
// Хранилище ключей
this.keys = {}
}
}Реализуем простейшую хэш-функцию:
// Преобразует ключ в хэшированное значение
// (хэш-функция)
hash(key) {
// Для простоты в качестве хэша используется сумма кодов символов ключа
// https://developer.mozilla.org/ru/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt
const hash = [...key].reduce((acc, char) => acc + char.charCodeAt(0), 0)
// Хэш (индекс) не должен превышать размера таблицы
return hash % this.buckets.length
}Метод установки значения по ключу:
// Устанавливает значение по ключу
set(key, value) {
// Хэшируем ключ
// (получаем индекс массива)
const index = this.hash(key)
// Сохраняем хэш по ключу
this.keys[key] = index
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
// (значением узла является объект)
const node = bucket.find({ cb: (value) => value.key === key })
// Если узел не найден
if (!node) {
// Добавляем новый узел
bucket.append({ key, value })
} else {
// Иначе, обновляем значение узла
node.value.value = value
}
}Метод удаления значения по ключу:
// Удаляет значение по ключу
remove(key) {
// Хэшируем ключ
const index = this.hash(key)
// Удаляем хэш по ключу
delete this.keys[key]
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
const node = bucket.find({ cb: (value) => value.key === key })
// Возвращаем удаленный узел или `null`,
// если узел отсутствует
return node ? bucket.remove(node.value) : null
}Метод извлечения значения по ключу:
// Возвращает значение по ключу
get(key) {
// Хэшируем ключ
const index = this.hash(key)
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
const node = bucket.find({ cb: (value) => value.key === key })
// Возвращаем значение узла или `null`,
// если узел отсутствует
return node ? node.value.value : null
}Напоследок реализуем несколько вспомогательных методов:
// Определяет наличие ключа
has(key) {
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/hasOwn
return Object.hasOwn(this.keys, key)
}
// Возвращает все ключи
getKeys() {
return Object.keys(this.keys)
}
// Возвращает все значения
getValues() {
// Перебираем списки и возвращаем значения всех узлов
return this.buckets.reduce((acc, bucket) => {
return acc.concat(
// Метод `toArray` преобразует связный список в массив
bucket.toArray().map((node) => node.value.value),
)
}, [])
}
Полный код хэш-таблицы:
// Импортируем конструктор связного списка
// (мы будем использовать метод цепочек для разрешения коллизий)
import LinkedList from './linked-list'
// Дефолтный размер таблицы
// (в реальности размер будет намного больше)
const defaultSize = 32
// Хэш-таблица
export default class HashTable {
constructor(size = defaultSize) {
// Создаем таблицу указанного размера и
// заполняем ее пустыми связными списками
this.buckets = new Array(size).fill(null).map(() => new LinkedList())
// Хранилище ключей
this.keys = {}
}
// Преобразует ключ в хэшированное значение
// (хэш-функция)
hash(key) {
// Для простоты в качестве хэша используется сумма кодов символов ключа
// https://developer.mozilla.org/ru/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt
const hash = [...key].reduce((acc, char) => acc + char.charCodeAt(0), 0)
// Хэшированное значение не должно превышать размера таблицы
return hash % this.buckets.length
}
// Устанавливает значение по ключу
set(key, value) {
// Хэшируем ключ
// (получаем индекс массива)
const index = this.hash(key)
// Сохраняем хэш по ключу
this.keys[key] = index
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
// (значением узла является объект)
const node = bucket.find({ cb: (value) => value.key === key })
// Если узел не найден
if (!node) {
// Добавляем новый узел
bucket.append({ key, value })
} else {
// Иначе, обновляем значение узла
node.value.value = value
}
}
// Удаляет значение по ключу
remove(key) {
// Хэшируем ключ
const index = this.hash(key)
// Удаляем хэш по ключу
delete this.keys[key]
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
const node = bucket.find({ cb: (value) => value.key === key })
// Возвращаем удаленный узел или `null`,
// если узел отсутствует
return node ? bucket.remove(node.value) : null
}
// Возвращает значение по ключу
get(key) {
// Хэшируем ключ
const index = this.hash(key)
// Извлекаем нужный список
const bucket = this.buckets[index]
// Извлекаем узел
const node = bucket.find({ cb: (value) => value.key === key })
// Возвращаем значение узла или `null`,
// если узел отсутствует
return node ? node.value.value : null
}
// Определяет наличие ключа
has(key) {
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/hasOwn
return Object.hasOwn(this.keys, key)
}
// Возвращает все ключи
getKeys() {
return Object.keys(this.keys)
}
// Возвращает все значения
getValues() {
// Перебираем списки и возвращаем значения всех узлов
return this.buckets.reduce((acc, bucket) => {
return acc.concat(
// Метод `toArray` преобразует связный список в массив
bucket.toArray().map((node) => node.value.value),
)
}, [])
}
}Тестирование
Проверяем, что наша хэш-таблица работает, как ожидается:
// data-structures/__tests__/hash-table.test.js
import HashTable from '../hash-table'
describe('HashTable', () => {
it('должен создать хэш-таблицы указанного размера', () => {
const defaultHashTable = new HashTable()
expect(defaultHashTable.buckets.length).toBe(32)
const biggerHashTable = new HashTable(64)
expect(biggerHashTable.buckets.length).toBe(64)
})
it('должен генерировать правильный хэш для ключей', () => {
const hashTable = new HashTable()
expect(hashTable.hash('a')).toBe(1)
expect(hashTable.hash('b')).toBe(2)
expect(hashTable.hash('abc')).toBe(6)
})
it('должен устанавливать, читать и удалять значения с коллизиями', () => {
const hashTable = new HashTable(3)
expect(hashTable.hash('a')).toBe(1)
expect(hashTable.hash('b')).toBe(2)
expect(hashTable.hash('c')).toBe(0)
expect(hashTable.hash('d')).toBe(1)
hashTable.set('a', 'sky-old')
hashTable.set('a', 'sky')
hashTable.set('b', 'sea')
hashTable.set('c', 'earth')
hashTable.set('d', 'ocean')
expect(hashTable.has('x')).toBe(false)
expect(hashTable.has('b')).toBe(true)
expect(hashTable.has('c')).toBe(true)
const stringifier = (value) => `${value.key}:${value.value}`
expect(hashTable.buckets[0].toString(stringifier)).toBe('c:earth')
expect(hashTable.buckets[1].toString(stringifier)).toBe('a:sky,d:ocean')
expect(hashTable.buckets[2].toString(stringifier)).toBe('b:sea')
expect(hashTable.get('a')).toBe('sky')
expect(hashTable.get('d')).toBe('ocean')
expect(hashTable.get('x')).toBeNull()
hashTable.remove('a')
expect(hashTable.remove('not-existing')).toBeNull()
expect(hashTable.get('a')).toBeNull()
expect(hashTable.get('d')).toBe('ocean')
hashTable.set('d', 'ocean-new')
expect(hashTable.get('d')).toBe('ocean-new')
})
it('должен добавить в таблицу объекты', () => {
const hashTable = new HashTable()
hashTable.set('objectKey', { prop1: 'a', prop2: 'b' })
const object = hashTable.get('objectKey')
expect(object).toBeDefined()
expect(object.prop1).toBe('a')
expect(object.prop2).toBe('b')
})
it('должен отслеживать актуальные ключи', () => {
const hashTable = new HashTable(3)
hashTable.set('a', 'sky-old')
hashTable.set('a', 'sky')
hashTable.set('b', 'sea')
hashTable.set('c', 'earth')
hashTable.set('d', 'ocean')
expect(hashTable.getKeys()).toEqual(['a', 'b', 'c', 'd'])
expect(hashTable.has('a')).toBe(true)
expect(hashTable.has('x')).toBe(false)
hashTable.remove('a')
expect(hashTable.has('a')).toBe(false)
expect(hashTable.has('b')).toBe(true)
expect(hashTable.has('x')).toBe(false)
})
it('должен вернуть все значения', () => {
const hashTable = new HashTable(3)
hashTable.set('a', 'alpha')
hashTable.set('b', 'beta')
hashTable.set('c', 'gamma')
expect(hashTable.getValues()).toEqual(['gamma', 'alpha', 'beta'])
})
it('должен вернуть все значения пустой таблицы', () => {
const hashTable = new HashTable()
expect(hashTable.getValues()).toEqual([])
})
it('должен вернуть все значения при наличии коллизий', () => {
const hashTable = new HashTable(3)
// Ключи `ab` и `ba` в текущей реализации будут иметь одинаковый хэш.
// Нужно убедиться в сериализации нескольких значений одного списка
hashTable.set('ab', 'one')
hashTable.set('ba', 'two')
hashTable.set('ac', 'three')
expect(hashTable.getValues()).toEqual(['one', 'two', 'three'])
})
})Запускаем тесты:
npm run test ./data-structures/__tests__/hash-tableРезультат:
Отлично! Двигаемся дальше.
6. Куча
Описание
Куча (heap) — это специализированная структура данных типа "дерево" (tree), которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то k(A) >= k(B), где k(X) — ключ (идентификатор) узла. Из этого следует, что элемент с наибольшим значением ключа всегда является корневым узлом (root node) кучи, поэтому такие кучи называют max-кучами (max heaps):
Приведенную max-кучу можно представить в виде массива следующим образом:
Если дерево перевернуть, то корневым узлом всегда будет элемент с наименьшим значением. Такие кучи называют min-кучами:
Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух (такие кучи называют "двоичными" или "бинарными" (binary)). Куча является максимально эффективной реализацией абстрактного типа данных, который называется "очередью с приоритетом" (см. следующий раздел). Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких, как алгоритм Дейкстры на d-кучах и сортировка методом пирамиды.
Интерактивную визуализации кучи можно посмотреть здесь.
Сложность
Временная сложность кучи зависит от ее типа.
| Тип кучи | find-max | delete-max | insert | increase-key | meld |
|---|---|---|---|---|---|
| Binary | Θ(1) |
Θ(log n) |
O(log n) |
O(log n) |
Θ(n) |
| Leftist | Θ(1) |
Θ(log n) |
Θ(log n) |
O(log n) |
Θ(log n) |
| Binomial | Θ(1) |
Θ(log n) |
Θ(1) |
O(log n) |
O(log n) |
| Fibonacci | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| Pairing | Θ(1) |
Θ(log n) |
Θ(1) |
o(log n) |
Θ(1) |
| Brodal | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| Rank-pairing | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| Strict Fibonacci | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| 2-3 heap | O(log n) |
O(log n) |
O(log n) |
Θ(1) |
? |
Где:
- find-max (или find-min): поиск максимального значения в max-куче или минимального значения в min-куче, соответственно (похоже на peek в очереди или стеке)
- delete-max (or delete-min): удаление корневого узла
- insert: добавление в кучу нового значения (похоже на push в стеке или enqueue в очереди)
- increase-key или decrease-key: обновление значения узла
- meld: объединение 2 куч в 1 с уничтожением оригиналов
Реализация
В рамках этой статьи мы рассмотрим реализацию только бинарной кучи.
Начнем с реализации родительского (или супер, или абстрактного) класса для min- и max-куч. Конструктор этого класса будет выглядеть следующим образом:
// data-structures/heap/index.js
// Импортируем конструктор функции сравнения узлов
import Comparator from '../../utils/comparator'
// Родительский класс для min- и max-куч
export default class Heap {
constructor(fn) {
// Кучи должны создаваться с помощью соответствующих подклассов
if (new.target === Heap) {
throw new TypeError('Кучу нельзя создавать напрямую!')
}
// Представление кучи в виде массива
this.heapContainer = []
// Функция сравнения элементов
this.compare = new Comparator(fn)
}
}Реализуем несколько вспомогательных методов:
// Возвращает индекс левого потомка
getLeftChildIndex(parentIndex) {
return 2 * parentIndex + 1
}
// Возвращает индекс правого потомка
getRightChildIndex(parentIndex) {
return 2 * parentIndex + 2
}
// Возвращает индекс предка
getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2)
}
// Проверяет наличие предка
hasParent(childIndex) {
return this.getParentIndex(childIndex) >= 0
}
// Проверяет наличие левого потомка
hasLeftChild(parentIndex) {
return this.getLeftChildIndex(parentIndex) < this.heapContainer.length
}
// Проверяет наличие правого потомка
hasRightChild(parentIndex) {
return this.getRightChildIndex(parentIndex) < this.heapContainer.length
}
// Возвращает левого потомка
leftChild(parentIndex) {
return this.heapContainer[this.getLeftChildIndex(parentIndex)]
}
// Возвращает правого потомка
rightChild(parentIndex) {
return this.heapContainer[this.getRightChildIndex(parentIndex)]
}
// Возвращает предка
parent(childIndex) {
return this.heapContainer[this.getParentIndex(childIndex)]
}
// Определяет пустоту кучи
isEmpty() {
return this.heapContainer.length === 0
}
// Возвращает строковое представление кучи
toString() {
return this.heapContainer.toString()
}Методы получения ссылки на корневой элемент кучи и самого корневого элемента:
// Возвращает ссылку на корневой элемент кучи
// (наименьший для min-кучи, наибольший для max-кучи;
// элемент не удаляется)
peek() {
if (this.isEmpty()) {
return null
}
return this.heapContainer[0]
}
// Удаляет и возвращает корневой элемент кучи
poll() {
if (this.isEmpty()) {
return null
}
if (this.heapContainer.length === 1) {
return this.heapContainer.pop()
}
const item = this.heapContainer[0]
// Перемещаем последний элемент в начало
this.heapContainer[0] = this.heapContainer.pop()
// Просеиваем кучу вниз
this.heapifyDown()
// Возвращаем удаленный элемент
return item
}Методы добавления и удаления элементов:
// Добавляет элемент в кучу
add(item) {
// Добавляем новый элемент в конец кучи
this.heapContainer.push(item)
// Просеиваем кучу вверх
this.heapifyUp()
return this
}
// Удаляет элемент из кучи.
// Принимает элемент и кастомную функцию сравнения элементов
remove(item, comparator = this.compare) {
// Определяем количество удаляемых элементов
const numberOfItemsToRemove = this.find(item, comparator).length
for (let i = 0; i < numberOfItemsToRemove; i += 1) {
// Определять индекс удаляемого элемента необходимо на каждой итерации,
// поскольку куча каждый раз модифицируется
const index = this.find(item, comparator).pop()
// Последний элемент просто удаляется
if (index === this.heapContainer.length - 1) {
this.heapContainer.pop()
} else {
// Иначе, перемещаем последний элемент на освободившееся место
this.heapContainer[index] = this.heapContainer.pop()
// Получаем родительский элемент
const parentItem = this.parent(index)
// Если предок отсутствует или неправильно расположен,
// просеиваем кучу вниз
if (
this.hasLeftChild(index) &&
(!parentItem ||
this.pairIsInCorrectOrder(parentItem, this.heapContainer[index]))
) {
this.heapifyDown(index)
} else {
// Иначе, просеиваем кучу вверх
this.heapifyUp(index)
}
}
}
return this
}Метод поиска индексов элементов:
// Находит индексы всех элементов, равных `item`.
// Принимает искомый элемент и кастомную функцию сравнения элементов
find(item, comparator = this.compare) {
const indices = []
for (let i = 0; i < this.heapContainer.length; i += 1) {
if (comparator.equal(this.heapContainer[i], item)) {
indices.push(i)
}
}
return indices
}Метод перестановки элементов:
// Меняет элементы местами
swap(indexOne, indexTwo) {
const tmp = this.heapContainer[indexOne]
this.heapContainer[indexOne] = this.heapContainer[indexTwo]
this.heapContainer[indexTwo] = tmp
}Пришло время главных (и самых сложных для понимания) функций кучи.
Функция просеивания кучи вверх:
// Просеивает кучу вверх.
// Принимает кастомный индекс начальной позиции
heapifyUp(customStartIndex) {
// Берем последний элемент (последний в массиве или нижний левый в дереве)
// и поднимаем его наверх до тех пор, пока он не будет
// правильно расположен по отношению к предку
let currentIndex = customStartIndex || this.heapContainer.length - 1
while (
this.hasParent(currentIndex) &&
!this.pairIsInCorrectOrder(
this.parent(currentIndex),
this.heapContainer[currentIndex],
)
) {
this.swap(currentIndex, this.getParentIndex(currentIndex))
currentIndex = this.getParentIndex(currentIndex)
}
}Функция просеивания кучи вниз:
// Просеивает кучу вниз.
// Принимает кастомный индекс начальной позиции (по умолчанию 0)
heapifyDown(customStartIndex = 0) {
// Сравниваем предка с его потомками и
// меняем местами предка с соответствующим потомком
// (наименьшим для min-кучи, наибольшим для max-кучи).
// Затем делаем тоже самое для следующего потомка
let currentIndex = customStartIndex
let nextIndex = null
// Пока есть левый потомок
while (this.hasLeftChild(currentIndex)) {
// Если есть правый потомок и
// потомки расположены в правильном порядке
if (
this.hasRightChild(currentIndex) &&
this.pairIsInCorrectOrder(
this.rightChild(currentIndex),
this.leftChild(currentIndex),
)
) {
// Следующим индексом является индекс правого потомка
nextIndex = this.getRightChildIndex(currentIndex)
} else {
// Иначе, следующим индексом является индекс левого потомка
nextIndex = this.getLeftChildIndex(currentIndex)
}
// Прерываем цикл, если элементы расположены в правильном порядке
if (
this.pairIsInCorrectOrder(
this.heapContainer[currentIndex],
this.heapContainer[nextIndex],
)
) {
break
}
// Меняем элементы местами
this.swap(currentIndex, nextIndex)
// Обновляем текущий индекс
currentIndex = nextIndex
}
}Заглушка (или абстрактный метод, или контракт) для метода определения правильного расположения элементов:
// Проверяет, что пара элементов в куче расположена в правильном порядке.
// Для min-кучи первый элемент всегда должен быть меньше или равен второму.
// Для max-кучи первый элемент всегда должен быть больше или равен второму.
// Этот метод должен быть реализован соответствующими подклассами
// (min-кучей и max-кучей)
pairIsInCorrectOrder(firstElement, secondElement) {
throw new Error('Метод сравнения не реализован!')
}
Полный код кучи:
// Импортируем конструктор функции сравнения узлов
import Comparator from '../../utils/comparator'
// Родительский класс для min- и max-куч
export default class Heap {
constructor(fn) {
// Кучи должны создаваться с помощью соответствующих подклассов
if (new.target === Heap) {
throw new TypeError('Кучу нельзя создавать напрямую!')
}
// Представление кучи в виде массива
this.heapContainer = []
// Функция сравнения элементов
this.compare = new Comparator(fn)
}
// Возвращает индекс левого потомка
getLeftChildIndex(parentIndex) {
return 2 * parentIndex + 1
}
// Возвращает индекс правого потомка
getRightChildIndex(parentIndex) {
return 2 * parentIndex + 2
}
// Возвращает индекс предка
getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2)
}
// Проверяет наличие предка
hasParent(childIndex) {
return this.getParentIndex(childIndex) >= 0
}
// Проверяет наличие левого потомка
hasLeftChild(parentIndex) {
return this.getLeftChildIndex(parentIndex) < this.heapContainer.length
}
// Проверяет наличие правого потомка
hasRightChild(parentIndex) {
return this.getRightChildIndex(parentIndex) < this.heapContainer.length
}
// Возвращает левого потомка
leftChild(parentIndex) {
return this.heapContainer[this.getLeftChildIndex(parentIndex)]
}
// Возвращает правого потомка
rightChild(parentIndex) {
return this.heapContainer[this.getRightChildIndex(parentIndex)]
}
// Возвращает предка
parent(childIndex) {
return this.heapContainer[this.getParentIndex(childIndex)]
}
// Определяет пустоту кучи
isEmpty() {
return this.heapContainer.length === 0
}
// Возвращает строковое представление кучи
toString() {
return this.heapContainer.toString()
}
// Возвращает ссылку на корневой элемент кучи
// (наименьший для min-кучи, наибольший для max-кучи;
// элемент не удаляется)
peek() {
if (this.isEmpty()) {
return null
}
return this.heapContainer[0]
}
// Удаляет и возвращает корневой элемент кучи
poll() {
if (this.isEmpty()) {
return null
}
if (this.heapContainer.length === 1) {
return this.heapContainer.pop()
}
const item = this.heapContainer[0]
// Перемещаем последний элемент в начало
this.heapContainer[0] = this.heapContainer.pop()
// Просеиваем кучу вниз
this.heapifyDown()
// Возвращаем удаленный элемент
return item
}
// Добавляет элемент в кучу
add(item) {
// Добавляем новый элемент в конец кучи
this.heapContainer.push(item)
// Просеиваем кучу вверх
this.heapifyUp()
return this
}
// Удаляет элемент из кучи.
// Принимает элемент и кастомную функцию сравнения элементов
remove(item, comparator = this.compare) {
// Определяем количество удаляемых элементов
const numberOfItemsToRemove = this.find(item, comparator).length
for (let i = 0; i < numberOfItemsToRemove; i += 1) {
// Определять индекс удаляемого элемента необходимо на каждой итерации,
// поскольку куча каждый раз модифицируется
const index = this.find(item, comparator).pop()
// Последний элемент просто удаляется
if (index === this.heapContainer.length - 1) {
this.heapContainer.pop()
} else {
// Иначе, перемещаем последний элемент на освободившееся место
this.heapContainer[index] = this.heapContainer.pop()
// Получаем родительский элемент
const parentItem = this.parent(index)
// Если предок отсутствует или неправильно расположен,
// просеиваем кучу вниз
if (
this.hasLeftChild(index) &&
(!parentItem ||
this.pairIsInCorrectOrder(parentItem, this.heapContainer[index]))
) {
this.heapifyDown(index)
} else {
// Иначе, просеиваем кучу вверх
this.heapifyUp(index)
}
}
}
return this
}
// Находит индексы всех элементов, равных `item`.
// Принимает искомый элемент и кастомную функцию сравнения элементов
find(item, comparator = this.compare) {
const indices = []
for (let i = 0; i < this.heapContainer.length; i += 1) {
if (comparator.equal(this.heapContainer[i], item)) {
indices.push(i)
}
}
return indices
}
// Меняет элементы местами
swap(indexOne, indexTwo) {
const tmp = this.heapContainer[indexOne]
this.heapContainer[indexOne] = this.heapContainer[indexTwo]
this.heapContainer[indexTwo] = tmp
}
// Просеивает кучу вверх.
// Принимает кастомный индекс начальной позиции
heapifyUp(customStartIndex) {
// Берем последний элемент (последний в массиве или нижний левый в дереве)
// и поднимаем его наверх до тех пор, пока он не будет
// правильно расположен по отношению к предку
let currentIndex = customStartIndex || this.heapContainer.length - 1
while (
this.hasParent(currentIndex) &&
!this.pairIsInCorrectOrder(
this.parent(currentIndex),
this.heapContainer[currentIndex],
)
) {
this.swap(currentIndex, this.getParentIndex(currentIndex))
currentIndex = this.getParentIndex(currentIndex)
}
}
// Просеивает кучу вниз.
// Принимает кастомный индекс начальной позиции (по умолчанию 0)
heapifyDown(customStartIndex = 0) {
// Сравниваем предка с его потомками и
// меняем местами предка с соответствующим потомком
// (наименьшим для min-кучи и наибольшим для max-кучи).
// Затем делаем тоже самое для следующего потомка
let currentIndex = customStartIndex
let nextIndex = null
// Пока есть левый потомок
while (this.hasLeftChild(currentIndex)) {
// Если есть правый потомок и
// потомки расположены в правильном порядке
if (
this.hasRightChild(currentIndex) &&
this.pairIsInCorrectOrder(
this.rightChild(currentIndex),
this.leftChild(currentIndex),
)
) {
// Следующим индексом является индекс правого потомка
nextIndex = this.getRightChildIndex(currentIndex)
} else {
// Иначе, следующим индексом является индекс левого потомка
nextIndex = this.getLeftChildIndex(currentIndex)
}
// Прерываем цикл, если элементы расположены в правильном порядке
if (
this.pairIsInCorrectOrder(
this.heapContainer[currentIndex],
this.heapContainer[nextIndex],
)
) {
break
}
// Меняем элементы местами
this.swap(currentIndex, nextIndex)
// Обновляем текущий индекс
currentIndex = nextIndex
}
}
// Проверяет, что пара элементов в куче расположена в правильном порядке.
// Для min-кучи первый элемент всегда должен быть меньше или равен второму.
// Для max-кучи первый элемент всегда должен быть больше или равен второму.
// Этот метод должен быть реализован соответствующими подклассами
// (min-кучей и max-кучей)
pairIsInCorrectOrder(firstElement, secondElement) {
throw new Error('Метод сравнения не реализован!')
}
}Таким образом, реализация подклассов сводится к реализации метода pairIsInCorrectOrder.
Реализация подкласса min-кучи:
// data-structures/heap/min-heap.js
import Heap from '.'
export default class MinHeap extends Heap {
pairIsInCorrectOrder(firstElement, secondElement) {
// Первый элемент должен быть меньше или равен второму
return this.compare.lessThanOrEqual(firstElement, secondElement)
}
}Реализация подкласса max-кучи:
// data-structures/heap/max-heap.js
import Heap from '.'
export default class MaxHeap extends Heap {
pairIsInCorrectOrder(firstElement, secondElement) {
// Первый элемент должен быть больше или равен второму
return this.compare.greaterThanOrEqual(firstElement, secondElement)
}
}Тестирование
Проверим, что наша куча работает, как ожидается.
Начнем с суперкласса:
// data-structures/heap/__tests__/heap.test.js
import Heap from '..'
describe('Heap', () => {
it('должен выбросить исключение при попытке создания кучи напрямую', () => {
const instantiateHeap = () => {
const heap = new Heap()
heap.add(5)
}
expect(instantiateHeap).toThrow()
})
})
Тестирование min-кучи:
// data-structures/heap/__tests__/min-heap.test.js
import MinHeap from '../min-heap'
import Comparator from '../../../utils/comparator'
describe('MinHeap', () => {
it('должен создать пустую min-кучу', () => {
const minHeap = new MinHeap()
expect(minHeap).toBeDefined()
expect(minHeap.peek()).toBeNull()
expect(minHeap.isEmpty()).toBe(true)
})
it('должен добавить элементы в кучу и просеять ее вверх', () => {
const minHeap = new MinHeap()
minHeap.add(5)
expect(minHeap.isEmpty()).toBe(false)
expect(minHeap.peek()).toBe(5)
expect(minHeap.toString()).toBe('5')
minHeap.add(3)
expect(minHeap.peek()).toBe(3)
expect(minHeap.toString()).toBe('3,5')
minHeap.add(10)
expect(minHeap.peek()).toBe(3)
expect(minHeap.toString()).toBe('3,5,10')
minHeap.add(1)
expect(minHeap.peek()).toBe(1)
expect(minHeap.toString()).toBe('1,3,10,5')
minHeap.add(1)
expect(minHeap.peek()).toBe(1)
expect(minHeap.toString()).toBe('1,1,10,5,3')
expect(minHeap.poll()).toBe(1)
expect(minHeap.toString()).toBe('1,3,10,5')
expect(minHeap.poll()).toBe(1)
expect(minHeap.toString()).toBe('3,5,10')
expect(minHeap.poll()).toBe(3)
expect(minHeap.toString()).toBe('5,10')
})
it('должен извлечь элементы из кучи и просеять ее вниз', () => {
const minHeap = new MinHeap()
minHeap.add(5)
minHeap.add(3)
minHeap.add(10)
minHeap.add(11)
minHeap.add(1)
expect(minHeap.toString()).toBe('1,3,10,11,5')
expect(minHeap.poll()).toBe(1)
expect(minHeap.toString()).toBe('3,5,10,11')
expect(minHeap.poll()).toBe(3)
expect(minHeap.toString()).toBe('5,11,10')
expect(minHeap.poll()).toBe(5)
expect(minHeap.toString()).toBe('10,11')
expect(minHeap.poll()).toBe(10)
expect(minHeap.toString()).toBe('11')
expect(minHeap.poll()).toBe(11)
expect(minHeap.toString()).toBe('')
expect(minHeap.poll()).toBeNull()
expect(minHeap.toString()).toBe('')
})
it('должен просеять кучу вниз по правильной ветке', () => {
const minHeap = new MinHeap()
minHeap.add(3)
minHeap.add(12)
minHeap.add(10)
expect(minHeap.toString()).toBe('3,12,10')
minHeap.add(11)
expect(minHeap.toString()).toBe('3,11,10,12')
expect(minHeap.poll()).toBe(3)
expect(minHeap.toString()).toBe('10,11,12')
})
it('должен находить индексы элементов', () => {
const minHeap = new MinHeap()
minHeap.add(3)
minHeap.add(12)
minHeap.add(10)
minHeap.add(11)
minHeap.add(11)
expect(minHeap.toString()).toBe('3,11,10,12,11')
expect(minHeap.find(5)).toEqual([])
expect(minHeap.find(3)).toEqual([0])
expect(minHeap.find(11)).toEqual([1, 4])
})
it('должен удалять элементы из кучи с ее просеиванием вниз', () => {
const minHeap = new MinHeap()
minHeap.add(3)
minHeap.add(12)
minHeap.add(10)
minHeap.add(11)
minHeap.add(11)
expect(minHeap.toString()).toBe('3,11,10,12,11')
expect(minHeap.remove(3).toString()).toEqual('10,11,11,12')
expect(minHeap.remove(3).peek()).toEqual(10)
expect(minHeap.remove(11).toString()).toEqual('10,12')
expect(minHeap.remove(3).peek()).toEqual(10)
})
it('должен удалять элементы из кучи с ее просеиванием вверх', () => {
const minHeap = new MinHeap()
minHeap.add(3)
minHeap.add(10)
minHeap.add(5)
minHeap.add(6)
minHeap.add(7)
minHeap.add(4)
minHeap.add(6)
minHeap.add(8)
minHeap.add(2)
minHeap.add(1)
expect(minHeap.toString()).toBe('1,2,4,6,3,5,6,10,8,7')
expect(minHeap.remove(8).toString()).toEqual('1,2,4,6,3,5,6,10,7')
expect(minHeap.remove(7).toString()).toEqual('1,2,4,6,3,5,6,10')
expect(minHeap.remove(1).toString()).toEqual('2,3,4,6,10,5,6')
expect(minHeap.remove(2).toString()).toEqual('3,6,4,6,10,5')
expect(minHeap.remove(6).toString()).toEqual('3,5,4,10')
expect(minHeap.remove(10).toString()).toEqual('3,5,4')
expect(minHeap.remove(5).toString()).toEqual('3,4')
expect(minHeap.remove(3).toString()).toEqual('4')
expect(minHeap.remove(4).toString()).toEqual('')
})
it('должен удалить элементы из кучи, найденные с помощью кастомной функции сравнения', () => {
const minHeap = new MinHeap()
minHeap.add('dddd')
minHeap.add('ccc')
minHeap.add('bb')
minHeap.add('a')
expect(minHeap.toString()).toBe('a,bb,ccc,dddd')
const comparator = new Comparator((a, b) => {
if (a.length === b.length) {
return 0
}
return a.length < b.length ? -1 : 1
})
minHeap.remove('hey', comparator)
expect(minHeap.toString()).toBe('a,bb,dddd')
})
it('должен удалить элементы из кучи с правильной реструктуризацией дерева', () => {
const minHeap = new MinHeap()
minHeap.add(1)
minHeap.add(2)
minHeap.add(3)
minHeap.add(4)
minHeap.add(5)
minHeap.add(6)
minHeap.add(7)
minHeap.add(8)
minHeap.add(9)
expect(minHeap.toString()).toBe('1,2,3,4,5,6,7,8,9')
minHeap.remove(2)
expect(minHeap.toString()).toBe('1,4,3,8,5,6,7,9')
minHeap.remove(4)
expect(minHeap.toString()).toBe('1,5,3,8,9,6,7')
})
})
Тестирование max-кучи:
// data-structures/heap/__tests__/max-heap.test.js
import MaxHeap from '../max-heap'
import Comparator from '../../../utils/comparator'
describe('MaxHeap', () => {
it('должен создать пустую max-кучу', () => {
const maxHeap = new MaxHeap()
expect(maxHeap).toBeDefined()
expect(maxHeap.peek()).toBeNull()
expect(maxHeap.isEmpty()).toBe(true)
})
it('должен добавить элементы в кучу и просеять ее вверх', () => {
const maxHeap = new MaxHeap()
maxHeap.add(5)
expect(maxHeap.isEmpty()).toBe(false)
expect(maxHeap.peek()).toBe(5)
expect(maxHeap.toString()).toBe('5')
maxHeap.add(3)
expect(maxHeap.peek()).toBe(5)
expect(maxHeap.toString()).toBe('5,3')
maxHeap.add(10)
expect(maxHeap.peek()).toBe(10)
expect(maxHeap.toString()).toBe('10,3,5')
maxHeap.add(1)
expect(maxHeap.peek()).toBe(10)
expect(maxHeap.toString()).toBe('10,3,5,1')
maxHeap.add(1)
expect(maxHeap.peek()).toBe(10)
expect(maxHeap.toString()).toBe('10,3,5,1,1')
expect(maxHeap.poll()).toBe(10)
expect(maxHeap.toString()).toBe('5,3,1,1')
expect(maxHeap.poll()).toBe(5)
expect(maxHeap.toString()).toBe('3,1,1')
expect(maxHeap.poll()).toBe(3)
expect(maxHeap.toString()).toBe('1,1')
})
it('должен извлечь элементы из кучи и просеять ее вниз', () => {
const maxHeap = new MaxHeap()
maxHeap.add(5)
maxHeap.add(3)
maxHeap.add(10)
maxHeap.add(11)
maxHeap.add(1)
expect(maxHeap.toString()).toBe('11,10,5,3,1')
expect(maxHeap.poll()).toBe(11)
expect(maxHeap.toString()).toBe('10,3,5,1')
expect(maxHeap.poll()).toBe(10)
expect(maxHeap.toString()).toBe('5,3,1')
expect(maxHeap.poll()).toBe(5)
expect(maxHeap.toString()).toBe('3,1')
expect(maxHeap.poll()).toBe(3)
expect(maxHeap.toString()).toBe('1')
expect(maxHeap.poll()).toBe(1)
expect(maxHeap.toString()).toBe('')
expect(maxHeap.poll()).toBeNull()
expect(maxHeap.toString()).toBe('')
})
it('должен просеять кучу вниз по правильной ветке', () => {
const maxHeap = new MaxHeap()
maxHeap.add(3)
maxHeap.add(12)
maxHeap.add(10)
expect(maxHeap.toString()).toBe('12,3,10')
maxHeap.add(11)
expect(maxHeap.toString()).toBe('12,11,10,3')
expect(maxHeap.poll()).toBe(12)
expect(maxHeap.toString()).toBe('11,3,10')
})
it('должен находить индексы элементов', () => {
const maxHeap = new MaxHeap()
maxHeap.add(3)
maxHeap.add(12)
maxHeap.add(10)
maxHeap.add(11)
maxHeap.add(11)
expect(maxHeap.toString()).toBe('12,11,10,3,11')
expect(maxHeap.find(5)).toEqual([])
expect(maxHeap.find(12)).toEqual([0])
expect(maxHeap.find(11)).toEqual([1, 4])
})
it('должен удалять элементы из кучи с ее просеиванием вниз', () => {
const maxHeap = new MaxHeap()
maxHeap.add(3)
maxHeap.add(12)
maxHeap.add(10)
maxHeap.add(11)
maxHeap.add(11)
expect(maxHeap.toString()).toBe('12,11,10,3,11')
expect(maxHeap.remove(12).toString()).toEqual('11,11,10,3')
expect(maxHeap.remove(12).peek()).toEqual(11)
expect(maxHeap.remove(11).toString()).toEqual('10,3')
expect(maxHeap.remove(10).peek()).toEqual(3)
})
it('должен удалять элементы из кучи с ее просеиванием вверх', () => {
const maxHeap = new MaxHeap()
maxHeap.add(3)
maxHeap.add(10)
maxHeap.add(5)
maxHeap.add(6)
maxHeap.add(7)
maxHeap.add(4)
maxHeap.add(6)
maxHeap.add(8)
maxHeap.add(2)
maxHeap.add(1)
expect(maxHeap.toString()).toBe('10,8,6,7,6,4,5,3,2,1')
expect(maxHeap.remove(4).toString()).toEqual('10,8,6,7,6,1,5,3,2')
expect(maxHeap.remove(3).toString()).toEqual('10,8,6,7,6,1,5,2')
expect(maxHeap.remove(5).toString()).toEqual('10,8,6,7,6,1,2')
expect(maxHeap.remove(10).toString()).toEqual('8,7,6,2,6,1')
expect(maxHeap.remove(6).toString()).toEqual('8,7,1,2')
expect(maxHeap.remove(2).toString()).toEqual('8,7,1')
expect(maxHeap.remove(1).toString()).toEqual('8,7')
expect(maxHeap.remove(7).toString()).toEqual('8')
expect(maxHeap.remove(8).toString()).toEqual('')
})
it('должен удалить элементы из кучи, найденные с помощью кастомной функции сравнения', () => {
const maxHeap = new MaxHeap()
maxHeap.add('a')
maxHeap.add('bb')
maxHeap.add('ccc')
maxHeap.add('dddd')
expect(maxHeap.toString()).toBe('dddd,ccc,bb,a')
const comparator = new Comparator((a, b) => {
if (a.length === b.length) {
return 0
}
return a.length < b.length ? -1 : 1
})
maxHeap.remove('hey', comparator)
expect(maxHeap.toString()).toBe('dddd,a,bb')
})
})Запускаем тесты:
npm run test ./data-structures/heapРезультат:
7. Очередь с приоритетом
Описание
Очередь с приоритетом (priority queue) — это абстрактный тип данных, похожий на обычную очередь (см. часть 1, раздел 3) или стек (см. часть 1, раздел 4), за исключением того, что в ней каждый элемент имеет определенный "приоритет" (priority). Элемент с более высоким приоритетом обрабатывается перед элементом с более низким приоритетом. Если два элемента имеют одинаковый приоритет, они обрабатываются в порядке их расположения в очереди.
Несмотря на то, что очереди с приоритетом часто реализуются с помощью куч, они концептуально различаются. Очередь с приоритетом — это абстрактная концепция, вроде "списка" (list) или "карты" (map). Как список может быть реализован с помощью связного списка (см. часть 1, раздел 1) или массива, так и очередь с приоритетом может быть реализована с помощью кучи или другим способом, например, с помощью неупорядоченного массива.
Интерактивную визуализации очереди с приоритетом можно посмотреть здесь.
Сложность
Временная сложность очереди с приоритетом составляет O(n) или O(n*log(n)) (зависит от реализации).
Реализация
Для реализации очереди с приоритетом мы воспользуемся min-кучей (см. предыдущий раздел).
Начнем с конструктора:
// data-structures/priority-queue.js
// Импортируем конструктор функции сравнения узлов
import Comparator from '../utils/comparator'
// Импортируем конструктор min-кучи
import MinHeap from './heap/min-heap'
// Очередь с приоритетом.
// Реализация на основе min-кучи
export default class PriorityQueue extends MinHeap {
constructor() {
// Инициализируем min-кучу
super()
// Карта приоритетов
this.priorities = new Map()
// Функция сравнения элементов
this.compare = new Comparator(this.comparePriorities.bind(this))
}
}Методы добавления и удаления элементов в/из очереди:
// Добавляет элемент в очередь.
// Принимает элемент и приоритет.
// Чем больше приоритет (меньше значение `priority`),
// тем "выше" элемент находится в очереди
add(item, priority = 0) {
// Обновляем приоритеты
this.priorities.set(item, priority)
// Добавляем элемент в кучу
super.add(item)
return this
}
// Удаляет элемент из очереди.
// Принимает элемент и кастомную функцию сравнения элементов
remove(item, compare) {
// Удаляем элемент из кучи
super.remove(item, compare)
// Обновляем приоритеты
this.priorities.delete(item)
return this
}Метод обновления приоритета:
// Обновляет приоритет.
// Принимает элемент и новый приоритет
changePriority(item, priority) {
// Удаляем элемент из очереди
this.remove(item, new Comparator(this.compareValues))
// Добавляем элемент с новым приоритетом
this.add(item, priority)
return this
}Метод поиска элемента по значению и определения наличия элемента:
// Ищет элемент по значению.
// Возвращает массив индексов
findByValue(item) {
return this.find(item, new Comparator(this.compareValues))
}
// Определяет наличие элемента
hasValue(item) {
return this.findByValue(item).length > 0
}Методы сравнения элементов по приоритетам и значениям:
// Сравнивает приоритеты
comparePriorities(a, b) {
// Вызываем функцию сравнения значений,
// передавая ей приоритеты
return this.compareValues(this.priorities.get(a), this.priorities.get(b))
}
// Сравнивает значения
compareValues(a, b) {
if (a === b) {
return 0
}
return a < b ? -1 : 1
}
Полный код очереди с приоритетом:
// Импортируем конструктор функции сравнения узлов
import Comparator from '../utils/comparator'
// Импортируем конструктор min-кучи
import MinHeap from './heap/min-heap'
// Очередь с приоритетом.
// Реализация на основе min-кучи
export default class PriorityQueue extends MinHeap {
constructor() {
// Инициализируем min-кучу
super()
// Карта приоритетов
this.priorities = new Map()
// Функция сравнения элементов
this.compare = new Comparator(this.comparePriorities.bind(this))
}
// Добавляет элемент в очередь.
// Принимает элемент и приоритет.
// Чем больше приоритет (меньше значение `priority`),
// тем "выше" элемент находится в очереди
add(item, priority = 0) {
// Обновляем приоритеты
this.priorities.set(item, priority)
// Добавляем элемент в кучу
super.add(item)
return this
}
// Удаляет элемент из очереди.
// Принимает элемент и кастомную функцию сравнения элементов
remove(item, compare) {
// Удаляем элемент из кучи
super.remove(item, compare)
// Обновляем приоритеты
this.priorities.delete(item)
return this
}
// Обновляет приоритет.
// Принимает элемент и новый приоритет
changePriority(item, priority) {
// Удаляем элемент из очереди
this.remove(item, new Comparator(this.compareValues))
// Добавляем элемент с новым приоритетом
this.add(item, priority)
return this
}
// Ищет элемент по значению.
// Возвращает массив индексов
findByValue(item) {
return this.find(item, new Comparator(this.compareValues))
}
// Определяет наличие элемента
hasValue(item) {
return this.findByValue(item).length > 0
}
// Сравнивает приоритеты
comparePriorities(a, b) {
// Вызываем функцию сравнения значений,
// передавая ей приоритеты
return this.compareValues(this.priorities.get(a), this.priorities.get(b))
}
// Сравнивает значения
compareValues(a, b) {
if (a === b) {
return 0
}
return a < b ? -1 : 1
}
}Тестирование
Проверяем, что наша очередь с приоритетом работает, как ожидается:
import PriorityQueue from '../priority-queue'
describe('PriorityQueue', () => {
it('должен создать дефолтную очередь с приоритетом', () => {
const priorityQueue = new PriorityQueue()
expect(priorityQueue).toBeDefined()
})
it('должен добавить элементы с приоритетом в очередь', () => {
const priorityQueue = new PriorityQueue()
priorityQueue.add(10, 1)
expect(priorityQueue.peek()).toBe(10)
priorityQueue.add(5, 2)
expect(priorityQueue.peek()).toBe(10)
priorityQueue.add(100, 0)
expect(priorityQueue.peek()).toBe(100)
})
it('должен добавить в очередь объекты', () => {
const priorityQueue = new PriorityQueue()
const user1 = { name: 'Mike' }
const user2 = { name: 'Bill' }
const user3 = { name: 'Jane' }
priorityQueue.add(user1, 1)
expect(priorityQueue.peek()).toBe(user1)
priorityQueue.add(user2, 2)
expect(priorityQueue.peek()).toBe(user1)
priorityQueue.add(user3, 0)
expect(priorityQueue.peek()).toBe(user3)
})
it('должен извлечь элементы из очереди согласно приоритету', () => {
const priorityQueue = new PriorityQueue()
priorityQueue.add(10, 1)
priorityQueue.add(5, 2)
priorityQueue.add(100, 0)
priorityQueue.add(200, 0)
expect(priorityQueue.poll()).toBe(100)
expect(priorityQueue.poll()).toBe(200)
expect(priorityQueue.poll()).toBe(10)
expect(priorityQueue.poll()).toBe(5)
})
it('должен обновить приоритеты головных узлов', () => {
const priorityQueue = new PriorityQueue()
priorityQueue.add(10, 1)
priorityQueue.add(5, 2)
priorityQueue.add(100, 0)
priorityQueue.add(200, 0)
expect(priorityQueue.peek()).toBe(100)
priorityQueue.changePriority(100, 10)
priorityQueue.changePriority(10, 20)
expect(priorityQueue.poll()).toBe(200)
expect(priorityQueue.poll()).toBe(5)
expect(priorityQueue.poll()).toBe(100)
expect(priorityQueue.poll()).toBe(10)
})
it('должен обновить приоритеты внутренних узлов', () => {
const priorityQueue = new PriorityQueue()
priorityQueue.add(10, 1)
priorityQueue.add(5, 2)
priorityQueue.add(100, 0)
priorityQueue.add(200, 0)
expect(priorityQueue.peek()).toBe(100)
priorityQueue.changePriority(200, 10)
priorityQueue.changePriority(10, 20)
expect(priorityQueue.poll()).toBe(100)
expect(priorityQueue.poll()).toBe(5)
expect(priorityQueue.poll()).toBe(200)
expect(priorityQueue.poll()).toBe(10)
})
it('должен обновить приоритеты и добавить элемент', () => {
const priorityQueue = new PriorityQueue()
priorityQueue.add(10, 1)
priorityQueue.add(5, 2)
priorityQueue.add(100, 0)
priorityQueue.add(200, 0)
priorityQueue.changePriority(200, 10)
priorityQueue.changePriority(10, 20)
priorityQueue.add(15, 15)
expect(priorityQueue.poll()).toBe(100)
expect(priorityQueue.poll()).toBe(5)
expect(priorityQueue.poll()).toBe(200)
expect(priorityQueue.poll()).toBe(15)
expect(priorityQueue.poll()).toBe(10)
})
it('должен определить наличие значений элементов', () => {
const priorityQueue = new PriorityQueue()
priorityQueue.add(10, 1)
priorityQueue.add(5, 2)
priorityQueue.add(100, 0)
priorityQueue.add(200, 0)
priorityQueue.add(15, 15)
expect(priorityQueue.hasValue(70)).toBe(false)
expect(priorityQueue.hasValue(15)).toBe(true)
})
})Запускаем тесты:
npm run test ./data-structures/__tests__/priority-queueРезультат:
8. Префиксное дерево
Префиксное дерево (или бор, или луч, или нагруженное дерево) (trie) — структура данных, позволяющая хранить ассоциативный массив (или другое динамическое множество), ключами которого чаще всего являются строки. Представляет собой корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все ребра, соединяющие этот узел с его потомками, помечены разными символами. Некоторые узлы префиксного дерева выделены и считается, что префиксное дерево содержит данную строку-ключ тогда и только тогда, когда эту строку можно прочитать на пути из корня до некоторого (единственного для этой строки) выделенного узла.
Таким образом, в отличие от бинарных деревьев поиска (binary search tree), ключ, идентифицирующий конкретный узел дерева, не явно хранится в данном узле, а задается положением данного узла в дереве. Получить ключ можно выписыванием символов, помечающих ребра на пути от корня до узла. Ключ корневого узла — пустая строка. Часто в выделенных узлах хранят дополнительную информацию, связанную с ключом, и обычно выделенными являются только листья, а иногда и некоторые внутренние узлы.
Сложность
Временная сложность префиксного дерева составляет O(n) (при использовании хэш-таблицы).
Реализация
Для реализации префиксного дерева мы будем использовать хэш-таблицу (см. раздел 5).
Начнем с узла дерева:
// data-structures/trie/node.js
// Импортируем конструктор хэш-таблицы
import HashTable from '../hash-table'
// Последний (завершающий) символ
export const HEAD_CHARACTER = '*'
// Узел префиксного дерева
export default class Node {
constructor(char, isCompleteWord = false) {
// Символ
this.char = char
// Индикатор завершающего символа
this.isCompleteWord = isCompleteWord
// Хэш-таблица потомков
this.children = new HashTable()
}
}Методы добавления и удаления узлов-потомков:
// Добавляет потомка в дерево
addChild(char, isCompleteWord = false) {
// Добавляем узел при отсутствии
if (!this.hasChild(char)) {
this.children.set(char, new Node(char, isCompleteWord))
}
// Извлекаем узел
const node = this.getChild(char)
// Обновляем флаг `isCompleteWord` при необходимости,
// например, при добавлении слова "car" после слова "carpet",
// букву "r" нужно пометить как завершающую
node.isCompleteWord = node.isCompleteWord || isCompleteWord
// Возвращаем узел
return node
}
// Удаляет потомка
removeChild(char) {
// Извлекаем узел
const node = this.getChild(char)
// Удаляем узел, только если:
// - у него нет потомков
// - node.isCompleteWord === false
if (node && !node.isCompleteWord && !node.hasChildren()) {
this.children.remove(char)
}
return this
}Вспомогательные методы для работы с потомками:
// Возвращает потомка
getChild(char) {
return this.children.get(char)
}
// Определяет наличие потомка
hasChild(char) {
return this.children.has(char)
}
// Определяет наличие потомков
hasChildren() {
return this.children.getKeys().length > 0
}
// Автодополнение (предложение следующих символов)
suggestChildren() {
return [...this.children.getKeys()]
}Метод преобразования потомков в строку:
// Преобразует потомков в строку
// с указанием признака завершающего символа
toString() {
let childrenAsString = this.suggestChildren().toString()
childrenAsString = childrenAsString ? `:${childrenAsString}` : ''
const isCompleteString = this.isCompleteWord ? HEAD_CHARACTER : ''
return `${this.char}${isCompleteString}${childrenAsString}`
}
Полный код узла префиксного дерева:
// Импортируем конструктор хэш-таблицы
import HashTable from '../hash-table'
// Последний (завершающий) символ
export const HEAD_CHARACTER = '*'
// Узел префиксного дерева
export default class Node {
constructor(char, isCompleteWord = false) {
// Символ
this.char = char
// Индикатор завершающего символа
this.isCompleteWord = isCompleteWord
// Хэш-таблица потомков
this.children = new HashTable()
}
// Добавляет потомка в дерево
addChild(char, isCompleteWord = false) {
// Добавляем узел при отсутствии
if (!this.hasChild(char)) {
this.children.set(char, new Node(char, isCompleteWord))
}
// Извлекаем узел
const node = this.getChild(char)
// Обновляем флаг `isCompleteWord` при необходимости,
// например, при добавлении слова "car" после слова "carpet",
// букву "r" нужно пометить как завершающую
node.isCompleteWord = node.isCompleteWord || isCompleteWord
// Возвращаем узел
return node
}
// Удаляет потомка
removeChild(char) {
// Извлекаем узел
const node = this.getChild(char)
// Удаляем узел, только если:
// - у него нет потомков
// - node.isCompleteWord === false
if (node && !node.isCompleteWord && !node.hasChildren()) {
this.children.remove(char)
}
return this
}
// Возвращает потомка
getChild(char) {
return this.children.get(char)
}
// Определяет наличие потомка
hasChild(char) {
return this.children.has(char)
}
// Определяет наличие потомков
hasChildren() {
return this.children.getKeys().length > 0
}
// Автодополнение (предложение следующих символов)
suggestChildren() {
return [...this.children.getKeys()]
}
// Преобразует потомков в строку
// с указанием признака завершающего символа
toString() {
let childrenAsString = this.suggestChildren().toString()
childrenAsString = childrenAsString ? `:${childrenAsString}` : ''
const isCompleteString = this.isCompleteWord ? HEAD_CHARACTER : ''
return `${this.char}${isCompleteString}${childrenAsString}`
}
}Отлично! Приступаем к реализации самого дерева:
// data-structures/trie/index.js
import TrieNode, { HEAD_CHARACTER } from './node'
// Префиксное дерево
export default class Trie {
constructor() {
// Головной (корневой) узел
this.head = new TrieNode(HEAD_CHARACTER)
}
}Методы добавления и удаления слова (ключа) в/из дерева:
// Добавляет слово (ключ) в дерево
addWord(word) {
// Преобразуем строку (слово) в массив символов
// (вопрос на засыпку: почему лучше не использовать `split('')`?
// Подсказка: попробуйте преобразовать "Hello, 👋!")
const chars = [...word]
// Текущий узел (начинаем с головного)
let node = this.head
// Перебираем символы и добавляем каждый в дерево
for (let i = 0; i < chars.length; i++) {
// Индикатор завершающего символа
const isComplete = i === chars.length - 1
// Добавляем потомка
node = node.addChild(chars[i], isComplete)
}
return this
}
// Удаляет слово (ключ) из дерева
removeWord(word) {
// Удаляет слово рекурсивно ("сначала в глубину")
const depthFirstRemove = (node, i = 0) => {
// Если удаляемый символ находится за пределами слова,
// ничего не делаем
if (i >= word.length) return
// Символ
const char = word[i]
// Следующий узел
const nextNode = node.getChild(char)
// Если следующий узел отсутствует,
// ничего не делаем
if (!nextNode) return
// Погружаемся глубже
depthFirstRemove(nextNode, i + 1)
// Поскольку мы удаляем слово,
// необходимо обновить флаг `isCompleteWord`
// его последнего символа
if (i === word.length - 1) {
nextNode.isCompleteWord = false
}
// Узел удаляется, только если:
// - у него нет потомков
// - nextNode.isCompleteWord === false
node.removeChild(char)
}
// Начинаем с головного узла
depthFirstRemove(this.head)
return this
}Метод автодополнения:
// Автодополнение (предложение следующих символов)
suggestNextCharacters(word) {
// Получаем последний символ
const lastChar = this.getLastCharNode(word)
// Если последний символ отсутствует
if (!lastChar) {
return null
}
// Возвращаем массив следующих символов
return lastChar.suggestChildren()
}Вспомогательный метод определения наличия слова в дереве:
// Определяет наличие слова в дереве
doesWordExist(word) {
// Получаем последний символ
const lastChar = this.getLastCharNode(word)
return Boolean(lastChar) && lastChar.isCompleteWord
}Наконец, метод получения последнего символа:
// Возвращает последний символ
getLastCharNode(word) {
// Разбиваем слово на символы
const chars = [...word]
// Текущий узел (начинаем с головного)
let node = this.head
// Перебираем символы
for (let i = 0; i < chars.length; i++) {
// Если символ отсутствует
if (!node.hasChild(chars[i])) {
return null
}
// Извлекаем потомка
node = node.getChild(chars[i])
}
// Возвращаем последний узел
return node
}
Полный код префиксного дерева:
import TrieNode, { HEAD_CHARACTER } from './node'
// Префиксное дерево
export default class Trie {
constructor() {
// Головной (корневой) узел
this.head = new TrieNode(HEAD_CHARACTER)
}
// Добавляет слово (ключ) в дерево
addWord(word) {
// Преобразуем строку (слово) в массив символов
// (вопрос на засыпку: почему лучше не использовать `split()`?
// Подсказка: попробуйте преобразовать "Hello, 👋!")
const chars = [...word]
// Текущий узел (начинаем с головного)
let node = this.head
// Перебираем символы и добавляем каждый в дерево
for (let i = 0; i < chars.length; i++) {
// Индикатор последнего (завершающего) символа
const isComplete = i === chars.length - 1
// Добавляем потомка
node = node.addChild(chars[i], isComplete)
}
return this
}
// Удаляет слово (ключ) из дерева
removeWord(word) {
// Удаляет слово рекурсивно ("сначала в глубину")
const depthFirstRemove = (node, i = 0) => {
// Если удаляемый символ находится за пределами слова,
// ничего не делаем
if (i >= word.length) return
// Символ
const char = word[i]
// Следующий узел
const nextNode = node.getChild(char)
// Если следующий узел отсутствует,
// ничего не делаем
if (!nextNode) return
// Погружаемся глубже
depthFirstRemove(nextNode, i + 1)
// Поскольку мы удаляем слово,
// необходимо обновить флаг `isCompleteWord`
// его последнего символа
if (i === word.length - 1) {
nextNode.isCompleteWord = false
}
// Узел удаляется, только если:
// - у него нет потомков
// - nextNode.isCompleteWord === false
node.removeChild(char)
}
// Начинаем с головного узла
depthFirstRemove(this.head)
return this
}
// Автодополнение (предложение следующих символов)
suggestNextCharacters(word) {
// Получаем последний символ
const lastChar = this.getLastCharNode(word)
// Если последний символ отсутствует
if (!lastChar) {
return null
}
// Возвращаем массив следующих символов
return lastChar.suggestChildren()
}
// Определяет наличие слова в дереве
doesWordExist(word) {
// Получаем последний символ
const lastChar = this.getLastCharNode(word)
return Boolean(lastChar) && lastChar.isCompleteWord
}
// Возвращает последний символ
getLastCharNode(word) {
// Разбиваем слово на символы
const chars = [...word]
// Текущий узел (начинаем с головного)
let node = this.head
// Перебираем символы
for (let i = 0; i < chars.length; i++) {
// Если символ отсутствует
if (!node.hasChild(chars[i])) {
return null
}
// Извлекаем потомка
node = node.getChild(chars[i])
}
// Возвращаем последний узел
return node
}
}Тестирование
Проверяем, что наше префиксное дерево работает, как ожидается.
Тестирование узла:
// data-structures/trie/__tests__/node.test.js
import TrieNode from '../node'
describe('TrieNode', () => {
it('должен создать узел префиксного дерева', () => {
const trieNode = new TrieNode('c', true)
expect(trieNode.char).toBe('c')
expect(trieNode.isCompleteWord).toBe(true)
expect(trieNode.toString()).toBe('c*')
})
it('должен добавить потомков', () => {
const trieNode = new TrieNode('c')
trieNode.addChild('a', true)
trieNode.addChild('o')
expect(trieNode.toString()).toBe('c:a,o')
})
it('должен извлечь потомков', () => {
const trieNode = new TrieNode('c')
trieNode.addChild('a')
trieNode.addChild('o')
expect(trieNode.getChild('a').toString()).toBe('a')
expect(trieNode.getChild('a').char).toBe('a')
expect(trieNode.getChild('o').toString()).toBe('o')
expect(trieNode.getChild('b')).toBeNull()
})
it('должен определить наличие потомков', () => {
const trieNode = new TrieNode('c')
expect(trieNode.hasChildren()).toBe(false)
trieNode.addChild('a')
expect(trieNode.hasChildren()).toBe(true)
})
it('должен определить наличие конкретного потомка', () => {
const trieNode = new TrieNode('c')
trieNode.addChild('a')
trieNode.addChild('o')
expect(trieNode.hasChild('a')).toBe(true)
expect(trieNode.hasChild('o')).toBe(true)
expect(trieNode.hasChild('b')).toBe(false)
})
it('должен получить следующие символы', () => {
const trieNode = new TrieNode('c')
trieNode.addChild('a')
trieNode.addChild('o')
expect(trieNode.suggestChildren()).toEqual(['a', 'o'])
})
it('должен удалить потомка, если у него НЕТ потомков', () => {
const trieNode = new TrieNode('c')
trieNode.addChild('a')
expect(trieNode.hasChild('a')).toBe(true)
trieNode.removeChild('a')
expect(trieNode.hasChild('a')).toBe(false)
})
it('НЕ должен удалять потомков, у которых есть потомки', () => {
const trieNode = new TrieNode('c')
trieNode.addChild('a')
const childNode = trieNode.getChild('a')
childNode.addChild('r')
trieNode.removeChild('a')
expect(trieNode.hasChild('a')).toEqual(true)
})
it('НЕ должен удалять потомков, которые являются завершающими символами', () => {
const trieNode = new TrieNode('c')
const IS_COMPLETE_WORD = true
trieNode.addChild('a', IS_COMPLETE_WORD)
trieNode.removeChild('a')
expect(trieNode.hasChild('a')).toEqual(true)
})
})
Тестирование дерева:
// data-structures/trie/__tests__/trie.test.js
import Trie from '..'
describe('Trie', () => {
it('должен создать префиксное дерево', () => {
const trie = new Trie()
expect(trie).toBeDefined()
expect(trie.head.toString()).toBe('*')
})
it('должен добавить слова в дерево', () => {
const trie = new Trie()
trie.addWord('cat')
expect(trie.head.toString()).toBe('*:c')
expect(trie.head.getChild('c').toString()).toBe('c:a')
trie.addWord('car')
expect(trie.head.toString()).toBe('*:c')
expect(trie.head.getChild('c').toString()).toBe('c:a')
expect(trie.head.getChild('c').getChild('a').toString()).toBe('a:t,r')
expect(trie.head.getChild('c').getChild('a').getChild('t').toString()).toBe(
't*',
)
})
it('должен удалить слова из дерева', () => {
const trie = new Trie()
trie.addWord('carpet')
trie.addWord('car')
trie.addWord('cat')
trie.addWord('cart')
expect(trie.doesWordExist('carpet')).toBe(true)
expect(trie.doesWordExist('car')).toBe(true)
expect(trie.doesWordExist('cart')).toBe(true)
expect(trie.doesWordExist('cat')).toBe(true)
// Пытаемся удалить несуществующее слово
trie.removeWord('carpool')
expect(trie.doesWordExist('carpet')).toBe(true)
expect(trie.doesWordExist('car')).toBe(true)
expect(trie.doesWordExist('cart')).toBe(true)
expect(trie.doesWordExist('cat')).toBe(true)
trie.removeWord('carpet')
expect(trie.doesWordExist('carpet')).toEqual(false)
expect(trie.doesWordExist('car')).toEqual(true)
expect(trie.doesWordExist('cart')).toBe(true)
expect(trie.doesWordExist('cat')).toBe(true)
trie.removeWord('cat')
expect(trie.doesWordExist('car')).toEqual(true)
expect(trie.doesWordExist('cart')).toBe(true)
expect(trie.doesWordExist('cat')).toBe(false)
trie.removeWord('car')
expect(trie.doesWordExist('car')).toEqual(false)
expect(trie.doesWordExist('cart')).toBe(true)
trie.removeWord('cart')
expect(trie.doesWordExist('car')).toEqual(false)
expect(trie.doesWordExist('cart')).toBe(false)
})
it('должен получить следующие символы', () => {
const trie = new Trie()
trie.addWord('cat')
trie.addWord('cats')
trie.addWord('car')
trie.addWord('caption')
expect(trie.suggestNextCharacters('ca')).toEqual(['t', 'r', 'p'])
expect(trie.suggestNextCharacters('cat')).toEqual(['s'])
expect(trie.suggestNextCharacters('cab')).toBeNull()
})
it('должен определить наличие слов', () => {
const trie = new Trie()
trie.addWord('cat')
trie.addWord('cats')
trie.addWord('carpet')
trie.addWord('car')
trie.addWord('caption')
expect(trie.doesWordExist('cat')).toBe(true)
expect(trie.doesWordExist('cats')).toBe(true)
expect(trie.doesWordExist('carpet')).toBe(true)
expect(trie.doesWordExist('car')).toBe(true)
expect(trie.doesWordExist('cap')).toBe(false)
expect(trie.doesWordExist('call')).toBe(false)
})
})Запускаем тесты:
npm run test ./data-structures/trieРезультат:
На сегодня это все, друзья. Увидимся в следующей части.
Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩
