Публикации по теме 'binary-heap'
Двоичные кучи и очереди приоритетов в JavaScript
Я работал в мастерской по ремонту компьютеров, где техники обрабатывали компьютеры в том порядке, в котором они поступали, в зависимости от того, сколько времени, по их прогнозам, займет ремонт. Каждый день у них был текущий список компьютеров, которые нужно было открыть и протестировать. Однако, если возникла чрезвычайная ситуация, когда клиенту потребовались его данные сразу, мы иногда могли выдвинуть его компьютер на передний план.
Технические специалисты использовали очередь..
Вопросы по теме 'binary-heap'
Объединение двух идеальных двоичных куч?
Я застрял на вопросе некоторое время и задавался вопросом, может ли кто-нибудь указать мне в правильном направлении:
Предположим, что двоичные кучи представлены с использованием представления дерева на основе указателей вместо массива....
2318 просмотров
schedule
09.08.2022
Почему куча лучше, чем бинарное дерево, для представления приоритетной очереди?
В (максимальной) куче легко найти самый большой элемент за O(1) время, но чтобы удалить его, вам потребуется сложность O(log(n)) .
Итак, если и вставка, и удаление из кучи равно O(log(n)) , каковы преимущества кучи по сравнению с двоичным...
1632 просмотров
schedule
12.11.2023
Построить бинарную кучу из массива, какой метод эффективнее и почему
Я изучаю кучи и нашел два способа их создания из заданного массива: я пытаюсь создать MAX Heap.
1. Подход сверху вниз
Здесь я просто проверяю каждый элемент, находится ли он в правильном положении или нет. Используя метод restoreUp, в котором...
1955 просмотров
schedule
05.06.2022
Max-Heapify бинарное дерево
Это один из вопросов интервью, с которым я недавно столкнулся.
Учитывая корневой адрес полного или почти полного двоичного дерева, мы должны написать функцию для преобразования дерева в максимальную кучу.
Здесь нет никаких массивов. Дерево уже...
27927 просмотров
schedule
08.04.2022
Поиск позиции узла двоичной кучи после вставки
Предполагая, что я хочу вставить узел в двоичную кучу, как я могу найти индекс узла в куче после вставки и кучи? Двоичная куча представлена в виде массива. Мне нужно найти этот алгоритм в O (log (log (n)).
Я знаю, как найти его в сложности log...
1356 просмотров
schedule
20.06.2022
Двоичная куча и приоритетные очереди
Я новичок в кучах, двоичной куче, и я пытаюсь понять, почему нам нужно реализовать приоритетную очередь с использованием двоичной кучи. Я также понимаю, что базовая структура данных Binary Heap снова является массивом.
Итак, мой вопрос: почему мы...
686 просмотров
schedule
30.06.2023
Измените алгоритм heapsort, чтобы извлекать k элементов за раз из кучи.
При выполнении пирамидальной сортировки только один максимальный элемент извлекается из кучи и заменяется элементом в конце кучи, после чего считается, что он находится вне кучи. Затем свойство кучи восстанавливается с помощью heapify. Это делается...
327 просмотров
schedule
22.04.2024
PriorityQueue Java показывает неожиданное поведение для дубликатов ключей, добавленных с более высоким приоритетом [дубликаты]
Я пытался реализовать слегка модифицированную версию алгоритма Джикстры, используя класс PriorityQueue для приоритетной очереди. Я столкнулся со странным поведением, которому нигде не мог найти объяснения. У меня есть подозрения на такое поведение,...
98 просмотров
schedule
02.07.2023
Какова конкретная цель использования максимальной кучи для приоритетной очереди
Максимальная куча используется для приоритетной очереди из-за дешевого извлечения максимального элемента.
Однако, пожалуйста, потерпите меня.
Разве мы не должны просто искать максимальный элемент за O(N) раз?
Я знаю, что для извлечения max...
51 просмотров
schedule
22.09.2023
Возникли проблемы с реализацией удаления в моей реализации Binary Heap/Priority Queue
Я пытаюсь реализовать метод удаления для моей реализации двоичной кучи.
class Node {
constructor(priority) {
this.priority = priority;
}
}
class PriorityQueue {
constructor() {
this.heap = [null];
}
remove() {
const toRemove =...
21 просмотров
schedule
21.04.2023
Амортизированная стоимость вставки/удаления в минимальной куче
Недавно я столкнулся с вопросом на собеседовании. никакая дополнительная информация не ставится под сомнение (возможно, следует использовать реализацию по умолчанию...)
Амортизированная стоимость n произвольных последовательностей операций...
338 просмотров
schedule
05.05.2022