Нахождение максимального элемента в минимальной куче - PullRequest
Новая
       14

Нахождение максимального элемента в минимальной куче

2 голосов
/ 22 января 2020

У меня минимальная куча: 

std::vector<int> h;
...
std::make_heap(h.begin(), h.end(), std::greater<int>());

Операции минимальной кучи std::push_heap и std::pop_heap - это то, что мне нужно в большинстве случаев, но в очень редких случаях мне нужно найти максимальный элемент в мин куча. Я могу сделать это с std::max_element: 

std::max_element(h.begin(), h.end());

Однако, это должно сканировать все элементы кучи.

Предлагает ли стандартная библиотека более эффективный алгоритм поиска элемента max в минимальной куче?

Ответы [ 2 ]

2 голосов
/ 22 января 2020

Если вам действительно нужна лучшая (т.е. сублинейная) временная сложность, рассмотрите возможность использования Min-max heap . Любой узел в этом дереве подчиняется следующему свойству:

Когда значение находится на уровне даже , тогда оно является наибольшим среди его потомков.
Когда значение находится на уровне odd , тогда оно является наименьшим среди его потомков.

Таким образом, root имеет наименьшее значение, и одно из двух children имеет наибольшее значение.

Временные сложности операций вставки / извлечения такие же, как и для минимальной кучи.

Проверка Существует ли реализация C ++ MinMax Heap?

2 голосов
/ 22 января 2020

TL; DR В мин-куче максимальный элемент находится в листовом узле X . Следовательно, вы можете ограничить свой поиск примерно половиной элементов кучи, т. Е. Ограничив свой поиск максимального элемента только конечными узлами: 

auto max_it = std::max_element(first_leaf_it, h.end());

Обратите внимание, что это по-прежнему занимает линейное время, но постоянный коэффициент примерно в два раза меньше, чем при сканировании всех элементов.

Ниже приведена реализация алгоритма, подобного STL, для нахождения максимального элемента в минимальной куче, предоставляемого итератором. pair: 

template<typename RandomIt>
auto min_heap_max_element(RandomIt first, RandomIt last) {
   auto n = last - first;

   if (n < 2)
      return first;

   auto first_leaf_it = first + (n - 2) / 2 + 1;
   return std::max_element(first_leaf_it, last);
}

Чтобы использовать его с вашим примером: 

auto max_it = min_heap_max_element(h.begin(), h.end());

Как найти первый листовой узел в куче

Последний элемент кучи - тот, на который указывает h.end(), - явно листовой узел , а его родительский элемент - последний неконечный узел , потому что если бы был не листовой узел, следующий за этим, элемент, который мы предположили как последний элемент кучи, не будет последним элементом, что является противоречием.

Следовательно, первый листовой узел будет элементом t сразу после родителя последнего узла.

Вы можете легко узнать, где находится родительский узел последнего узла: учитывая i индекс элемента кучи, его родитель находится в индексе (i - 1) / 2 . Итак, индекс последнего неконечного узла равен (h.size() - 2) / 2, а индекс первого конечного узла равен (h.size() - 2) / 2 + 1.

X Предположим, что максимальный элемент в min-куче расположен вместо этого в неконцевом узле . Это будет означать, что у него есть, по крайней мере, дочерний узел. Из-за свойства min-heap этот дочерний узел должен быть больше или равен своему родительскому узлу. Если дочерний узел больше, чем его родитель - который является максимальным элементом - дочерний узел больше максимального. Это невозможно, потому что у нас есть противоречие. Таким образом, все его дочерние узлы также должны быть максимальными, и так далее для этих дочерних узлов. Таким образом, в конце концов, существует максимум, расположенный в одном из конечных узлов, если максимальное значение повторяется в куче или единственное максимальное значение должно соответствовать конечному узлу.

...