Каковы наиболее известные границы для сравнения двух двоичных куч на равенство?

#computer-science #binary-heap

#информатика #двоичная куча

Вопрос:

В частности, без изменения входных данных.

Я до сих пор ничего не смог найти по этому вопросу, интересно, есть ли у него решение лучше, чем очевидное время O (n log n).

1. Как вы определяете равенство двух куч? Наиболее очевидным определением равенства было бы O (n), поскольку вы просто проверили бы, равны ли два массива. Или вы подразумеваете под равенством, что сортировка обеих куч приведет к равным последовательностям?

2. @MoB. Что повторяющиеся pop_max операции будут давать одни и те же значения. Сортировка и сравнение будут работать. Прямое сравнение не работает, потому что кучи представлены массивами 3 1 2 и 3 2 1 должны сравниваться равными. Тем не менее, существует некоторая общая структура, мне интересно, использовалась ли она.

Ответ №1:

Согласно вашему определению, две кучи равны, если они дают одну и ту же последовательность элементов при многократном извлечении их максимального элемента. Поскольку это равносильно деструктивной сортировке элементов в куче, равенство также эквивалентно утверждению, что две последовательности элементов кучи при сортировке равны. Но это эквивалентно многомножному равенству между двумя кучами.

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

Поскольку невозможно проверить равенство, не рассматривая каждый элемент хотя бы один раз, O (n) также является самой жесткой границей для проверки равенства двух двоичных куч.