Блог

Главная - Вопросы по программированию - Строительные кучи снизу вверх

Строительные кучи снизу вверх

#heap

#куча

Вопрос:

Я работаю над вопросом, в котором у меня есть 10 ключей, и я должен создать конструкцию снизу вверх. Согласно моей книге, я должен построить (n 1) / 2 кучи, что составляет 11/2 = 5,5 куч для нижней части. Затем 11/4 для 2-го уровня, 11/8 для 3-го и так далее.

Проблема в том, что я получаю это как результат:

(Используя ‘a’, например)

изображение кучи

Поскольку 11/2 = 5,5, то я округляю до 6, 11/4 = 2,75, то есть 3, 11/8 = 1,375, то есть 2, и 11/16 = 0,6875, то есть 1.

Даже если я не округляю, у меня все равно получаются странные кучи. Кто-нибудь может объяснить, где я напортачил?

Ответ №1:

Вы напортачили, потому что только последнему слою в двоичной куче разрешено быть неполным. Куча из 10 элементов должна выглядеть следующим образом:

         1
     /     
    2       3
   /      / 
  4    5  6   7
 /   /
8  9  10

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

  1. Узлы, не имеющие дочерних элементов, являются тривиальными кучами.
  2. Если узел имеет две дочерние кучи, мы можем преобразовать его в большую кучу с помощью операции пузырькового преобразования.

Итак, в начале мы знаем, что узлы на 4-м уровне (8, 9 и 10) уже являются кучами. Затем мы можем использовать это для пузырькового отображения узлов на третьем уровне, чтобы также превратить их в кучи и так далее.

Комментарии:

1. Я понимаю, что правильный ответ таков, но как я могу получить этот результат с помощью формулы, которую я использовал? Или, может быть, другая формула для достижения этого?

2. Я предполагаю, что эта формула должна работать только для полных куч (т. е.: n = 2 ^ k — 1)

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

4. Я на самом деле объяснил это. Разместите ключи в дереве в показанных позициях, но в том же порядке, в котором вы их получили. Дерево еще не является кучей, но вы знаете, что 4-й слой уже тривиально нагроможден. Затем вы выполняете операции пузырькования, чтобы увеличить третий ряд, а затем второй ряд и так далее.

5. Просто чтобы уточнить, было ли у меня 36 12 29… Я бы поставил 36 сверху, затем 12 и 29 на 2-м уровне? Затем, используя свойство heap, я бы поменял 36 на 12, сделав 12 корнем?