#data-structures #heap #min-heap
#структуры данных #куча #минимальная куча
Вопрос:
Минимальная куча состоит из 2047 элементов, максимальное количество сравнений, необходимых для определения максимального количества элементов, равно _.
Для этого я пошел с подходом, так как это минимальная куча, и элемент min будет находиться в корневом узле. Поэтому, чтобы найти максимальное «нет», мы должны дойти до конца дерева, то есть до уровня конечного узла, и должны сравнить со всеми. Таким образом, сравнение будет n-1, но ans-это не 2046, а 1043. Может ли кто-нибудь объяснить мне, как это сделать?
Комментарии:
1. Я чувствую, что вы, возможно, неправильно набрали 1043 для 1023. 1023 должно быть минимальное количество сравнений.
2. Да, я ошибся, это должно было быть 1023. Спасибо!
Ответ №1:
Вы совершенно правы в том, что максимальное число в минимальной куче должно быть одним из конечных узлов этой кучи (это должен быть конечный узел, хотя это может быть любой конечный узел). Куча-это полное двоичное дерево, и в случае 2047 элементов это будет идеальное дерево (в комплекте с полностью заполненным последним уровнем). В таком дереве на нижнем уровне кучи будет ровно 1024 элемента, что даст нам 1024 кандидата на минимум.
Поскольку кучи являются полными деревьями, они обычно хранятся в виде массивов, где массив содержит значения каждого уровня кучи, хранящиеся последовательно. Например, уровень 0, корневое значение дерева, находится в индексе 0 массива, два значения уровня 1 хранятся в индексах 1 и 2, уровень 2 в следующих 4 индексах, уровень 3 в следующих 8 и так далее. Таким образом, все 1024 конечных узла кучи элементов 2047 будут сохранены в конечных 1024 индексах массива (индексы с 1023 по 2046). Поскольку вам нужно сравнить только эти элементы, так как вы знаете, что среди них максимальное значение, и поскольку вы можете сразу перейти к ним, используя доступ к базовому массиву O(1) по индексу, вам нужно всего 1023 сравнения между последними 1024 элементами, чтобы найти максимальное значение.
Ответ №2:
В минимальной куче, состоящей из 2047 элементов, имеется 1024 конечных узла. Чтобы найти максимальный элемент, вам нужно n-1 сравнений. Итак, вы сравниваете первые два элемента, выбираете больший элемент и сравниваете его со следующим и так далее. Следовательно, число сравнений будет равно 1024-1 = 1023.