0

Дано:

Начальный стек: [9,7,8,6,4,5,6,1,5]

Мы берем данные из стека и получается куча такого вида:

куча

Что нужно узнать

  1. количество способов, которыми мы можем вернуть данные обратно в стек, так чтобы при следующем извлечении у нас снова получалась бинарная куча отличная от начальной? Например первый способ, начиная с конца берем последовательно каждый элемент и отправляем его в стек.
  2. сколько бинарных максимальных куч можно построить из значений данного стека?
  3. как изменится количество куч во втором пункте, если мы прибавим/удалим элемент(ы), т.е. общее решение.

Буду благодарен любым комментариям, которые помогут ответить на поставленные вопросы.

3
  • Что такое "начиная с конца" для кучи? 11 фев 2018 в 23:29
  • с последнего индекса до нулевого. операция обратная той, через которую мы получили дерево
    – Jan Novak
    12 фев 2018 в 13:29
  • Не понял. Куча - это дерево, как вы сами сказали. Что такое "индекс" в дереве? 12 фев 2018 в 14:10

1 ответ 1

0

Ответ на первый пункт

arrangement_number = 0 desired_heap = [9, 7, 8, 6, 4, 2, 4, 1, 5]

for permutation in itertools.permutations(desired_heap): binary_heap = BinHeap() for item in permutation: binary_heap.insert(item) if binary_heap._hl == desired_heap: arrangement_number += 1

print("Total: ", arrangement_number)

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.