Является ли отсортированный массив мини-кучей? Какое минимальное значение max-heap?

Ответ 1

Массив, отсортированный с самого низкого на самый высокий, является мини-кучей при использовании реализации кучи на основе массива. Свойство heap, что родительский node больше, чем его дочерние узлы (2i + 1 и 2i + 2, используя массивы с нулевым основанием), выполняется для всех узлов, имеющих дочерние элементы.

Минимальное значение максимальной кучи находится в одном из листовых узлов, но вы не знаете, что. Поскольку минимум node не может, по определению, иметь какие-либо дочерние узлы, он должен быть листом. Однако свойство кучи не указывает, как листовые узлы сравниваются друг с другом, только с их родителями.

Ответ 2

Является ли отсортированный массив мини-кучей?

Да, если вы используете типичное хранилище кучи, хранящееся в массиве.

Где минимальное значение max-heap?

На одном из листьев. Что именно undefined.

Ответ 3

Вы можете реализовать двоичную кучу как массив для сравнения индекса я с 2 * я + 1 и 2 * я + 2 (i начинается с 0). в минимальной куче a [i] a [2 * я + 1] и a [i] а [2 * я + 2]

так

1. Сортированный массив - это минимальная куча.

2. У него нет конкретного индекса. Все, что мы знаем, что это просто лист

Я предлагаю вам прочитать это http://en.wikipedia.org/wiki/Binary_heap

Ответ 4

где - минимальное значение максимальной кучи?

Ans: Макс. куча может быть представлена ​​простым массивом с начальным индексом от 1 до n. 1-й элемент - это корень максимальной кучи. Свойство heap: node в индексе я оставил дочерний элемент в 2i, а правый - в 2i + 1 (если 2i и 2i + 1 меньше размера кучи, то есть длины массива).

Листовые узлы максимальной кучи находятся от индекса я + 1 до n. Здесь я = n/2; n - длина массива. И один из листовых узлов имеет минимальное значение.
Таким образом, мы можем найти минимальное значение максимальной кучи от значений a [i + 1] до [n]. Сложность времени для нахождения минимального значения - порядок (n-i).

Ответ 5

• сортированный массив - это мини-куча?

Если он упорядочен по возрастанию - да, вообще говоря, это куча минут, точнее - реализация массива двоичной кучи со следующими правилами:

• Детей node с индексом я можно найти в индексах 2i + 1 и 2i + 2
• Родитель node с индексом я может быть найден на индексе floor ((i-1)/2)

В то же время он не работает обратным образом - двоичная куча на основе массива не будет хранить отсортированный список.

• где минимальное значение максимальной кучи?

Он не определен, и вы не хотите, чтобы вы быстро ответили, когда вы храните свои ключи в кучу минут. Если вы хотите, чтобы иметь возможность заглянуть как минимум и максимум кучи в O (1) время, вы можете использовать классы, как MinMaxPriorityQueue в Java.

Ответ 6

Является ли отсортированный массив мини-кучей?

отсортированный массив - это мини-куча или макс-куча, но наоборот не соответствует действительности
min-heap или max-heap не обязательно отсортированы по массивам.

Каково минимальное значение max-heap?

max-heap (или очередь приоритетов) по определению обеспечивает максимальное значение из коллекции в O (1) раз. если кто-то должен получить минимальное значение из макс-кучи, то использование самой кучи в первую очередь для этой проблемы неверно. он, как ожидая, что стек обеспечивает доступ к FIFO или ожидает очереди для предоставления доступа к LIFO.

Но jfyi, min значение будет на одном из листьев дерева, образованного кучей. это может быть на любом поддереве. поэтому вам нужен еще один алгоритм, который займет больше времени O (1), чтобы найти его.

В качестве примечания:
Куча с n элементами может иметь от 1 до (n + 1)/2].
Если высота дерева, образованного кучей, равна h, то куча будет иметь до 2 ^ (h-1) листьев

Ответ 7

Массивы могут быть отсортированы в порядке возрастания или в порядке убывания. Утверждение "Сортированный массив - это мини-куча" является частично правильным. Правильная версия этого утверждения: "Массив, отсортированный в порядке возрастания, может обрабатываться как min-heap", а оператор дополнения - "Массив, отсортированный по убыванию, может рассматриваться как максимальная куча".

"Массив, отсортированный в порядке возрастания, можно рассматривать как min-heap"

Но помните, что "не все мини-кучи могут принимать форму массива, отсортированного в порядке возрастания".

И о минимальном значении максимальной кучи мы знаем только, что это присутствует в листах, и мы можем искать это в O (n)