Эти два кажутся очень похожими и имеют почти идентичную структуру. Какая разница? Каковы временные сложности для разных операций
Сколько разных max-куч существует для списка из nnn целых чисел? Пример: список [1, 2, 3, 4] Макс-куча может быть 4 3 2 1: 4 / \ 3 2 / 1 или 4 2 3 1: 4 / \ 2 3 / 1
Во многих обсуждениях двоичной кучи в качестве поддерживаемой операции для минимальной кучи обычно указывается только ключ уменьшения. Например, глава 6.1 CLR и эта страница википедии . Почему ключ увеличения обычно не указывается для min-heap? Я полагаю, что это можно сделать в O (высота),...
Скорее всего, этот вопрос задавался раньше. Это из CLRS (2-е изд) проблема 6.5-8 - Задайте алгоритм времени для объединения k отсортированных списков в один отсортированный список, где n - общее количество элементов во всех входных списках. (Подсказка: используйте минимальную кучу для слияния k-...
Мне нужна помощь в определении потенциальной функции для максимальной кучи, так что извлечение max завершается за время амортизации . Я должен добавить, что у меня нет хорошего понимания потенциального метода.O ( 1 )О(1)O(1) Я знаю, что функция вставки должна «платить» больше, чтобы уменьшить...
Рандомизированные связываемые кучи имеют операцию «соединение», которую мы затем используем для определения всех других операций, включая вставку. Вопрос в том, какова ожидаемая высота этого дерева с узлами?nnn Теорема 1 Гамбина и Малинковского « Рандомизированные смешиваемые приоритетные очереди»...