Публикации по теме 'binary-heap'


Двоичные кучи и очереди приоритетов в JavaScript
Я работал в мастерской по ремонту компьютеров, где техники обрабатывали компьютеры в том порядке, в котором они поступали, в зависимости от того, сколько времени, по их прогнозам, займет ремонт. Каждый день у них был текущий список компьютеров, которые нужно было открыть и протестировать. Однако, если возникла чрезвычайная ситуация, когда клиенту потребовались его данные сразу, мы иногда могли выдвинуть его компьютер на передний план. Технические специалисты использовали очередь..

Вопросы по теме 'binary-heap'

Объединение двух идеальных двоичных куч?
Я застрял на вопросе некоторое время и задавался вопросом, может ли кто-нибудь указать мне в правильном направлении: Предположим, что двоичные кучи представлены с использованием представления дерева на основе указателей вместо массива....
2318 просмотров
schedule 09.08.2022

Почему куча лучше, чем бинарное дерево, для представления приоритетной очереди?
В (максимальной) куче легко найти самый большой элемент за O(1) время, но чтобы удалить его, вам потребуется сложность O(log(n)) . Итак, если и вставка, и удаление из кучи равно O(log(n)) , каковы преимущества кучи по сравнению с двоичным...
1632 просмотров

Построить бинарную кучу из массива, какой метод эффективнее и почему
Я изучаю кучи и нашел два способа их создания из заданного массива: я пытаюсь создать MAX Heap. 1. Подход сверху вниз Здесь я просто проверяю каждый элемент, находится ли он в правильном положении или нет. Используя метод restoreUp, в котором...
1955 просмотров
schedule 05.06.2022

Max-Heapify бинарное дерево
Это один из вопросов интервью, с которым я недавно столкнулся. Учитывая корневой адрес полного или почти полного двоичного дерева, мы должны написать функцию для преобразования дерева в максимальную кучу. Здесь нет никаких массивов. Дерево уже...
27927 просмотров

Поиск позиции узла двоичной кучи после вставки
Предполагая, что я хочу вставить узел в двоичную кучу, как я могу найти индекс узла в куче после вставки и кучи? Двоичная куча представлена ​​в виде массива. Мне нужно найти этот алгоритм в O (log (log (n)). Я знаю, как найти его в сложности log...
1356 просмотров

Двоичная куча и приоритетные очереди
Я новичок в кучах, двоичной куче, и я пытаюсь понять, почему нам нужно реализовать приоритетную очередь с использованием двоичной кучи. Я также понимаю, что базовая структура данных Binary Heap снова является массивом. Итак, мой вопрос: почему мы...
686 просмотров

Измените алгоритм heapsort, чтобы извлекать k элементов за раз из кучи.
При выполнении пирамидальной сортировки только один максимальный элемент извлекается из кучи и заменяется элементом в конце кучи, после чего считается, что он находится вне кучи. Затем свойство кучи восстанавливается с помощью heapify. Это делается...
327 просмотров

PriorityQueue Java показывает неожиданное поведение для дубликатов ключей, добавленных с более высоким приоритетом [дубликаты]
Я пытался реализовать слегка модифицированную версию алгоритма Джикстры, используя класс PriorityQueue для приоритетной очереди. Я столкнулся со странным поведением, которому нигде не мог найти объяснения. У меня есть подозрения на такое поведение,...
98 просмотров
schedule 02.07.2023

Какова конкретная цель использования максимальной кучи для приоритетной очереди
Максимальная куча используется для приоритетной очереди из-за дешевого извлечения максимального элемента. Однако, пожалуйста, потерпите меня. Разве мы не должны просто искать максимальный элемент за O(N) раз? Я знаю, что для извлечения max...
51 просмотров

Возникли проблемы с реализацией удаления в моей реализации Binary Heap/Priority Queue
Я пытаюсь реализовать метод удаления для моей реализации двоичной кучи. class Node { constructor(priority) { this.priority = priority; } } class PriorityQueue { constructor() { this.heap = [null]; } remove() { const toRemove =...
21 просмотров

Амортизированная стоимость вставки/удаления в минимальной куче
Недавно я столкнулся с вопросом на собеседовании. никакая дополнительная информация не ставится под сомнение (возможно, следует использовать реализацию по умолчанию...) Амортизированная стоимость n произвольных последовательностей операций...
338 просмотров