Преобразование максимальной кучи в двоичное дерево поиска

Ответ 1

Сначала отметим, что мы можем - без потери общности - считать, что в нашем двоичном дереве мы имеем элементы 1,2,3,... 2^m-1. Итак, отныне мы предполагаем, что у нас есть эти числа.

Тогда моя попытка будет некоторой функцией для преобразования отсортированного массива (т.е. 1 2 3 4 5) в массив, представляющий отсортированное двоичное дерево.

В сортированном двоичном дереве с элементами (2^m)-1 мы всегда имеем, что "дно" дерева состоит из всех неравномерных чисел, например. для m=3:

     4
  2     6
 1 3   5 7

Это означает, что в соответствующем массиве мы имеем, что последние числа - все неравномерные числа:

4 2 6 1 3 5 7
      -------
         ^
         uneven numbers!

Таким образом, мы можем построить последнюю "строку" двоичного дерева, гарантируя, что последние 2^(m-1) числа в соответствующем массиве - все неравномерные числа. Итак, все, что нам нужно сделать для последней строки, - это построить функцию, которая перемещает все элементы в позициях с неравными индексами в последнюю строку.

Итак, давайте теперь предположим, что у нас есть подпрограмма, которая - с учетом отсортированного массива в качестве ввода - правильно устанавливает последнюю строку.

Затем мы можем вызвать подпрограмму для всего массива для построения последней строки, в то время как все остальные элементы будут отсортированы. Когда мы применяем эту процедуру для массива 1 2 3 4 5 6 7, мы имеем следующую ситуацию:

2 4 6 1 3 5 7
      -------
         ^
         correct!

После первого раунда мы применяем процедуру для оставшегося подмассива (а именно 2 4 6), который строит вторую последнюю "строку" нашего двоичного дерева, в то время как остальные элементы остаются неизменными, поэтому мы получаем следующее:

 now correct as well!
   v
  ---
4 2 6 1 3 5 7
      -------
         ^
         correct from run before

Итак, все, что нам нужно сделать, это построить функцию, которая правильно устанавливает последнюю строку (т.е. вторую половину массива)!

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

Таким образом, среда выполнения для массива размером n в целом:

O(n log n) + O(n/2 log n/2) + O(n/4 log n/4) + ..., что совпадает с O(n log n). Обратите внимание, что мы должны использовать алгоритм сортировки на месте, такой как Heapsort, чтобы весь этот материал работал полностью на месте.

Мне жаль, что я не могу это уточнить, но я думаю, вы можете получить эту идею.

Ответ 2

Пусть n = 2 ^m - 1. В линейном времени мы можем сделать max-heap и извлечь элементы двоичного дерева поиска в отсортированном порядке, поэтому лучшее, на что мы можем надеяться (предполагая алгоритмы на основе сравнения) - это O (n log n) время и O (1) пространство. Вот такой алгоритм.

• При j = n до 1, вытащите максимальный элемент из j-элемента max-heap и сохраните его в (недавно освобожденном) месте j. Это сортирует массив.

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

  а. Древовидные элементы меньше корня.

  б. Древовидные элементы больше корня.

  с. Объедините деревья, повернув листья меньше, чем корень, в положение (= три оборота), чтобы оставить подзадачу в два раза меньше (O (n)).

  (08 04 12 02 06 10 14 01 03 05 07 09 11 13 15)16(24 20 28 18 22 26 30 17 19 21 23 25 27 29 31)

  (08 04 12 02 06 10 14)16(24 20 28 18 22 26 30)01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

  (08 04 12)16(24 20 28)02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

  (08)16(24)04 12 20 28 02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

  16 08 24 04 12 20 28 02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

Ответ 3

Только некоторые основные идеи:

• Двоичное дерево поиска - это двоичное дерево.
• Оба родителя корня либо ниль, либо сами бинарные деревья поиска
• Значения удовлетворяют следующему условию: left child < root < правильный ребенок

Условие 1 не является проблемой - куча также является бинарным деревом. Условие 2 является проблематичным, но предполагает подход снизу вверх. Условие 3 также не выполняется.

Снизу вверх: - Мы начинаем со всех листьев - это непроблемно, они двоичные деревья поиска. - Теперь мы продолжим рекурсивную прогулку по каждому уровню родителей до корня. - Поменяйте поддеревья, если левый ребенок больше, чем правый. - Поменяйте корень с большим значением 2 детей (это правильный ребенок) - Этого может быть недостаточно - вам может потребоваться продолжить исправление правильного поддерева, пока он не станет двоичным деревом поиска.

Это должно сработать. Но все же - удаление верхнего элемента и вставка его в самобалансирующееся дерево будет более быстрым/лучшим подходом и намного проще реализовать (например, с использованием стандартных компонентов, таких как std:: map в С++).

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

Ответ 4

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