Описание тега binary-heap

Вопросы с тегом
1 ответ

Сравнение методов построения целого binayHeap из списка ключей

Читая пост о построении двоичной кучи. Я запутался в подходе1. Подход автора1(O(n*log n)): Учитывая список ключей, создайте двоичную кучу, вставляя каждый ключ по одному. Поскольку вы начинаете со списка из одного элемента, список сортируется, и вы …
22 ноя '18 в 18:32
0 ответов

Какой контейнер я должен выбрать для реализации кучи?

Я пытаюсь сделать свои собственные библиотеки в C++ и хочу реализовать структуру данных кучи. Я уже закодировал все алгоритмы для вставки, удаления и поиска для кучи Мне нужен контейнер для кучи. Я знаю, что они реализованы как массивы, но так как м…
24 июн '14 в 06:13
1 ответ

Почему deleteMin из кучи берет O(logn)?

На слайде лекций моего класса у меня есть куча, и у нее есть метод, называемый deleteMin(). Что он делает, он удаляет минимальное значение в куче. И это говорит, что требуется O(logn). Это я не могу понять. В структуре кучи минимальное значение всег…
31 июл '17 в 14:21
2 ответа

Почему эта сортировка лучше всего подходит для внешней сортировки?

При изучении алгоритмов сортировки это называется сортировкой кучи, используемой для внешней сортировки. Я не могу понять, чем она отличается с точки зрения методов сортировки, когда мы имеем дело с внешним хранилищем? Или что это за то, что сортиро…
05 янв '18 в 16:01
3 ответа

Как сохранить порядок элементов с одинаковым приоритетом в очереди приоритетов, реализованной в виде двоичной кучи?

Я создал двоичную кучу, которая представляет приоритетную очередь. Это просто классический известный алгоритм. Эта куча планирует хронологическую последовательность различных событий (ключ сортировки - время). Он поддерживает 2 операции: вставить и …
02 авг '11 в 09:04
2 ответа

Оператор перегрузки скорее всего не работает

Не могли бы вы, ребята, проверить мою функцию что-то неправильное (), и мои операторы перегрузки. Иногда, когда я запускаю функцию что-то не так (), я получаю "True", а иногда "False". Я ничего не меняю, почему это происходит? Это график алгоритма Д…
05 мар '13 в 03:15
1 ответ

Java реализует очередь приоритетов с использованием ошибок двоичной кучи

У меня проблема с домашним заданием: Создан HeapPriorityQueue, который будет реализовывать приоритетную очередь import java.util.Arrays; public class HeapPriorityQueue<K,V extends Comparable<K>> implements PriorityQueue<K, V> { pri…
08 сен '13 в 12:39
1 ответ

Реализация пользовательского двоичного дерева кучи - случайное удаление узла

Я пытался решить этот вопрос. Задача - это немного настраиваемого двоичного дерева кучи, если сравнить его с определением ADT двоичного дерева кучи. В двоичном дереве кучи вы всегда выполняете deleteMax/deletetMin в зависимости от вида дерева кучи, …
08 янв '18 в 03:15
2 ответа

Реализация сопоставимого интерфейса (Java) в программе Binary heaps в курсе алгоритмов Принстонского университета

Я не использую обширную Java для программирования, просто имею базовые знания языка. Я делаю этот курс по алгоритмам на Coursera: https://www.coursera.org/learn/algorithms-part1/ Программа для двоичной кучи, приведенная в этом курсе: public class Ma…
24 июл '18 в 11:27
1 ответ

Докажите, что максимальное сравнение двоичной кучи составляет (2N-2)

Я пытаюсь доказать, что для двоичных куч, buildHeap делает не более (2N-2) сравнения между элементами. Мне очень трудно доказать это утверждение.
11 апр '18 в 11:42
1 ответ

Фибоначчи против Бинарное повышение производительности кучи в методе Fast Marching

Я сейчас этот вопрос задавал много раз. Тем не менее, я не могу найти решение для моей конкретной проблемы. Я реализовал метод быстрого марширования (очень похожий на Дейкстру) в C++11 и два разных варианта: с кучей Фибоначчи и двоичной кучей. Для э…
08 апр '14 в 12:34
4 ответа

Временная сложность или Big O кода

У меня есть этот массив, который имеет свойство максимальной кучи. Временная сложность deleteMax составляет O(logn). Если приведенный ниже код будет повторяться только 7 раз, какова будет временная сложность приведенного ниже кода (большой O)? int h…
12 апр '17 в 05:25
1 ответ

Heapq с равным приоритетом

Я пытаюсь создать модное событие. Таким образом, я должен определить класс Event который наследуется моими разными событиями. class Event: def __init__(self, last_instant): self.last_instant = last_instant # That's the prio criteria class Event1(Eve…
06 авг '18 в 11:25
1 ответ

Удалить произвольный элемент из кучи в Python

Есть ли реализация двоичной кучи, где я могу вытолкнуть другие элементы, кроме корня, в log n раз? Я использую heapq - но heap.index( wKeys ) в heap.pop( heap.index( wKeys ) ) очень медленно Мне нужна двоичная куча для моей проблемы - где я когда-ни…
05 мар '18 в 15:58
1 ответ

Среда выполнения Python heapify

Я изучаю структуры данных и алгоритмы, в которых я должен был реализовать алгоритм heapsort для запуска в определенный период времени. Ниже приведены две реализации: def generateSwaps(): size=self._n for root in range((size//2)-1,-1,-1): root_val = …
16 авг '17 в 01:26
2 ответа

Как я могу проверить, является ли список минимальной двоичной кучи (Java)?

Здравствуйте, мне нужна помощь для моей домашней работы. Как я могу проверить, является ли список минимальной двоичной кучей? Пожалуйста, скажите мне, если я сделал это правильно: public boolean check(int [] arr){ if(arr[0]==null){ return false; } f…
23 июн '17 в 12:35
1 ответ

Построение дерева Хаффмана с использованием двоичной кучи

В настоящее время я пытаюсь написать программу, которая читает текстовый файл и кодирует его, создав HuffmanTree. Я использую параллельные массивы в двоичной куче очереди с приоритетами и для отслеживания моих деревьев Хаффмана. Я знаю принцип удале…
22 окт '18 в 19:26
1 ответ

Кучи и деревья бинарного поиска

Какое время выполнения связано с (Max-heapify), который реализован с использованием k-ary heap. Является ли k-арная куча более эффективной, чем асимптотически говоря, двоичная куча? Является ли k-ary куча более эффективной, чем двоичная куча на прак…
18 апр '15 в 19:16
2 ответа

Бинарные кучи против д-арых куч

Я читал, что двоичные кучи быстрее при минимальных операциях удаления, а d-ary - быстрее при операциях с уменьшением приоритета (хотя я не понимаю, почему), но потом я также прочитал, что 4-куча быстрее при они оба по сравнению с двоичной кучей. Так…
18 мар '15 в 15:42
1 ответ

Как изменить приоритет значения в max-heap?

Я пишу максимальную кучу, которая может изменить приоритет / значение. Однако у меня есть проблемы, чтобы понять, что не так в моем коде. Я следовал за этим в качестве ссылки: ref Это мой код (я скрыл некоторые функции, так как здесь не фокус) stati…
05 апр '16 в 05:53