Куча (Heap)

Куча — это специализированная структура данных на основе дерева, которая удовлетворяет свойству кучи:

Существует два основных типа куч:

1. Max Heap (max-куча): Значение родительского узла должно быть больше либо равно значениям дочерних узлов.

2. Min Heap (min-куча): Значение родительского узла должно быть меньше либо равно значениям дочерних узлов.

Мы сосредоточимся на max-куче, так как большинство стандартных библиотек используют max-кучу для реализации очередей с приоритетами. В max-куче корень дерева — это наибольший элемент, а листья — наименьшие. При этом особого порядка среди листьев может не быть. Единственное, в чём мы уверены, — это то, что корень содержит наибольшее значение, а все его дочерние узлы не превосходят это значение.

Обратите внимание, что последняя строка в куче всегда заполняется слева направо. То есть сперва заполняется самый левый лист, и только в конце — самый правый лист, как показано на рисунке выше.

Реализация

Кучу можно реализовать в виде массива, где первый элемент массива соответствует корню. Поскольку у каждого узла всего 2 дочерних узла, мы можем использовать следующую логику индексов:

1. Корневой элемент имеет индекс 1.

2. Левые и правые потомки находятся по индексам 2i и 2i+1 соответственно.

3. Родительский узел элемента с индексом i расположен по индексу i // 2.

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

# Просто считайте каждую строку на рисунке и запишите числа подряд
heap = [None, 8, 5, 7, 1, 1, 6, 3, 1]

# Или, чтобы было нагляднее
heap = [None,      # Пропускаем индекс [0] для упрощения нумерации
        8,         # Индекс   [1]
    5,       7,    # Индексы  [2, 3]
  1,  1,   6,  3,  # Индексы  [4, 5, 6, 7]
1]                 # Индекс   [8]

Задача: проверить, является ли двоичное дерево кучей

Дано двоичное дерево, представленное массивом из n чисел (в соответствии с описанным индексированием). Нужно проверить, удовлетворяет ли оно свойствам max-кучи.

Входные данные

В первой строке входных данных содержится одно целое число n (1 ≤ n ≤ 100 000).

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

Выходные данные

Программа должна вывести Yes, если заданное двоичное дерево удовлетворяет свойствам max-кучи, и No — в противном случае.

Примеры

Пояснение

Пример 1

Пример 2