Куча — это специализированная структура данных на основе дерева, которая удовлетворяет свойству кучи:
🗼
Если P — это родительский узел для C, то значение P должно быть больше или равно (для max-кучи) или меньше или равно (для min-кучи) значению C.
Пример max-кучи с 8 узлами
Существует два основных типа куч:
Max Heap (max-куча): Значение родительского узла должно быть больше либо равно значениям дочерних узлов.
Min Heap (min-куча): Значение родительского узла должно быть меньше либо равно значениям дочерних узлов.
Мы сосредоточимся на max-куче, так как большинство стандартных библиотек используют max-кучу для реализации очередей с приоритетами. В max-куче корень дерева — это наибольший элемент, а листья — наименьшие. При этом особого порядка среди листьев может не быть. Единственное, в чём мы уверены, — это то, что корень содержит наибольшее значение, а все его дочерние узлы не превосходят это значение.
Обратите внимание, что последняя строка в куче всегда заполняется слева направо. То есть сперва заполняется самый левый лист, и только в конце — самый правый лист, как показано на рисунке выше.
Реализация
Кучу можно реализовать в виде массива, где первый элемент массива соответствует корню. Поскольку у каждого узла всего 2 дочерних узла, мы можем использовать следующую логику индексов:
Корневой элемент имеет индекс 1.
Левые и правые потомки находятся по индексам 2i и 2i+1 соответственно.
Родительский узел элемента с индексом 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 — в противном случае.
Примеры
Входные данные
Выходные данные
8
8 5 7 1 1 6 3 1
Yes
7
8 5 7 1 9 6 3
No
Пояснение
Пример 1
All the parent nodes have a value larger than or equal to their child nodes. Therefore, the heap property is satisfied.
Пример 2
The node with a value of 9 is larger than its parent node. Therefore, the heap property is not satisfied.
