Кучи , также известные как приоритетная очередь, это абстрактный тип данных. Концептуально это двоичное дерево, в котором дочерние элементы каждого узла меньше или равны самому узлу. (Предполагая, что это максимальная куча.) Когда элемент перемещается или выталкивается, куча перестраивается, так что самый большой элемент - следующий. Его легко реализовать в виде дерева или массива.

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

[90, 15, 10, 7, 12, 2]

Действительно, это двоичное дерево, организованное в виде массива. Это потому, что у каждого элемента есть дети. 90 имеет двоих детей, 15 и 10 лет.

       15, 10,
[(90),         7, 12, 2]

15 также имеет детей, 7 и 12:

               7, 12,
[90, (15), 10,        2]

10 имеет детей:

                      2
[90, 15, (10), 7, 12,  ]

и следующим элементом также будет ребенок 10 лет, за исключением того, что там нет места. 7, 12 и 2 также имели бы потомков, если бы массив был достаточно длинным. Вот еще один пример кучи:

[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

И вот визуализация дерева, которое делает предыдущий массив:

На случай, если этого недостаточно, вот явная формула для получения дочерних элементов i-го элемента.

//0-indexing:
child1 = (i * 2) + 1
child2 = (i * 2) + 2

//1-indexing:
child1 = (i * 2)
child2 = (i * 2) + 1

Вы должны принять непустой массив в качестве входных данных и вывести истинное значение, если массив находится в порядке кучи, и ложное значение в противном случае. Это может быть куча с 0 индексами или куча с 1 индексом, если вы указываете, какой формат ожидает ваша программа / функция. Вы можете предположить, что все массивы будут содержать только положительные целые числа. Вы не можете использовать какие-либо кучи. Это включает, но не ограничивается

• Функции, которые определяют, находится ли массив в форме кучи
• Функции, которые преобразуют массив в кучу или в форму кучи
• Функции, которые принимают массив в качестве входных данных и возвращают структуру данных кучи

Вы можете использовать этот скрипт Python, чтобы проверить, находится ли массив в форме кучи или нет (0 проиндексировано):

def is_heap(l):
    for head in range(0, len(l)):
        c1, c2 = head * 2 + 1, head * 2 + 2
        if c1 < len(l) and l[head] < l[c1]:
            return False
        if c2 < len(l) and l[head] < l[c2]:
            return False

    return True

Тест IO:

Все эти входные данные должны возвращать True:

[90, 15, 10, 7, 12, 2]
[93, 15, 87, 7, 15, 5]
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[100, 19, 36, 17, 3, 25, 1, 2, 7]
[5, 5, 5, 5, 5, 5, 5, 5]

И все эти входные данные должны возвращать False:

[4, 5, 5, 5, 5, 5, 5, 5]
[90, 15, 10, 7, 12, 11]
[1, 2, 3, 4, 5]
[4, 8, 15, 16, 23, 42]
[2, 1, 3]

Как обычно, это код-гольф, поэтому применяются стандартные лазейки и выигрывает самый короткий ответ в байтах!

Желе, 11 9 5 байт

x2:ḊṂ

4 байта удалены благодаря Деннису!

Попробуй это здесь.

объяснение

x2          Duplicate each element.
:Ḋ          Each element divided by the input with the first element removed,
            as integer, so there is a 0 only if some element in the duplicated
            list is less than the corresponding element in the other.
            There are also elements left unchanged, but it doesn't matter as
            the input is all positive.
Ṃ           Minimum in the list.

JavaScript (ES6), 34 30 байт

a=>!a.some((e,i)=>e>a[i-1>>1])

Изменить: Исправление моего кода для уточнения спецификации стоит 1 байт, так что спасибо @ edc65 за сохранение 4 байта.

Haskell, 33 байта

f(a:b)=and$zipWith(<=)b$a:b<*"xx"

или

and.(zipWith(<=).tail<*>(<*"xx"))

J, 24 байта

*/@:<:]{~0}:@,<.@-:@i.@#

объяснение

*/@:<:]{~0}:@,<.@-:@i.@#  Input: s
                       #  Count of s
                    i.@   Create range [0, 1, ..., len(s)-1]
                 -:@      Halve each
              <.@         Floor each
         0   ,            Prepend a zero to it
          }:@             Remove the last value to get the parent indices of each
      ]                   Identity function to get s
       {~                 Take the values from s at the parent indices
    <:                    For each, 1 if it is less than or equal to its parent else 0
*/@:                      Reduce using multiplication and return

MATL , 13 12 байт

ttf2/k)>~4L)

Попробуйте онлайн! Или проверьте все тестовые случаи .

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

объяснение

t     % Take input implicitly. Duplicate
tf    % Duplicate and push indices of nonzero entries. This gives [1 2 ... n] where n
      % is input size
2/k   % Divide by 2 and round down
)     % Index into input. Gives array of parents, except for the first entry
>~    % True for entries of the input that don't exceed those in the array of parents
4L)   % Discard first entry

Python 2, 45 байт

f=lambda l:l==[]or l[len(l)/2-1]/l.pop()*f(l)

Выходы 0 для Falsy, ненулевые для Truthy.

Проверяет, что последний элемент меньше или равен своему родительскому элементу в индексе len(l)/2-1. Затем рекурсивно проверяется, что то же самое имеет значение True с удаленным последним элементом списка, и так далее, пока список не станет пустым.

48 байтов:

f=lambda l,i=1:l==l[:i]or l[~-i/2]/l[i]*f(l,i+1)

Проверяет, что в каждом индексе iэлемент является не более чем его родительским в индексе(i-1)/2 . Разделение по этажам дает 0, если это не так.

Выполнение базового варианта так же i/len(l)orдает одинаковую длину. Сначала я пробовал архивировать, но получил более длинный код (57 байт).

lambda l:all(map(lambda a,b,c:b<=a>=c,l,l[1::2],l[2::2]))

R 97 88 82 байта

Надеюсь, я правильно понял. Теперь посмотрим, смогу ли я избавиться от еще нескольких байтов. Бросил rbind и положил в саппли и правильно разбирался с вектором на основе 1.

Реализовано как безымянная функция

function(Y)all(sapply(1:length(Y),function(X)Y[X]>=Y[X*2]&Y[X]>=Y[X*2+1]),na.rm=T)

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

> f=
+ function(Y)all(sapply(1:length(Y),function(X)Y[X]>=Y[X*2]&Y[X]>=Y[X*2+1]),na.rm=T)
> f(c(90, 15, 10, 7, 12, 2))
[1] TRUE
> f(c(93, 15, 87, 7, 15, 5))
[1] TRUE
> f(c(10, 9, 8, 7, 6, 5, 4, 3, 2, 1))
[1] TRUE
> f(c(5, 5, 5, 5, 5, 5, 5, 5))
[1] TRUE
> f(c(4, 5, 5, 5, 5, 5, 5, 5))
[1] FALSE
> f(c(90, 15, 10, 7, 12, 11))
[1] FALSE
> f(c(4, 8, 15, 16, 23, 42))
[1] FALSE

CJam, 19 16 13 12 байт

q~_:_\(;./:*

Гольф от 3 байтов благодаря Деннису.

Попробуй это здесь.

Pyth, 8 байт

.AgV.i+h

       hQ      first element of input
      +  Q     plus input
    .i    Q    interleaved with input
  gV       Q   vectorized greater-than-or-equal comparison with input
.A             check if all results are true

Попробуйте онлайн

Сетчатка , 51 байт

\d+
$*
^(?!(1+ )*(1+) 1* ?(?<-1>1+ )*(?(1)(?!))1\2)

Попробуйте онлайн!

Принимает разделенный пробелами список чисел в качестве входных данных. Выходы 1/ 0для правдивых / ложных

C ++ 14, 134 105 байт

#define M(d) (2*i+d<c.size()&&(c[i]<c[2*i+d]||f(c,2*i+d)==0))
int f(auto&c,int i=0){return!(M(1)||M(2));}

Требуется cконтейнер для поддержки .operator[](int)и .size(), какstd::vector<int> .

Ungolfed:

int f(auto& c, int i=0) {
    if (2*i+1<c.size() && c[i] < c[2*i+1]) return 0;
    if (2*i+2<c.size() && c[i] < c[2*i+2]) return 0;
    if (2*i+1<c.size() && (f(c,2*i+1) == 0)) return 0;
    if (2*i+2<c.size() && (f(c,2*i+2) == 0)) return 0;
    return 1;
}

Может быть меньше, если допустимы истина 0и ложь 1.

R, 72 байта

Немного другой подход от другого R ответа .

x=scan();all(diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)<1,na.rm=T)

Считывает входные данные из стандартного ввода, создает вектор всех пар сравнения, вычитает их друг из друга и проверяет, является ли результат отрицательным числом или нулем.

объяснение

Прочитать ввод от stdin:

x=scan();

Создайте наши пары. Мы создаем индексы 1...N(где Nдлина x) для родительских узлов. Мы принимаем это дважды, так как каждый родитель имеет (максимально) двух детей. Мы также берем детей, (1...N)*2и (1...N)*2+1. Для индексов, превышающих длину x, R возвращает NA«недоступно». Для ввода 90 15 10 7 12 2этот код дает нам 90 15 10 7 12 2 90 15 10 7 12 2 15 7 2 NA NA NA 10 12 NA NA NA NA.

                  x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)]

В этом векторе пар каждый элемент имеет своего партнера на расстоянии N*2. Например, партнер позиции 1 находится в позиции 12 (6 * 2). Мы используем, diffчтобы рассчитать разницу между этими парами, указав lag=N*2для сравнения предметов с их правильными партнерами. Любые операции над NAэлементами просто возвращаются NA.

             diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)

Наконец, мы проверяем, что все эти возвращаемые значения меньше 1(то есть, что первое число, родитель, был больше, чем второе число, дочерний), исключая NAзначения из рассмотрения.

         all(diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)<1,na.rm=T)

На самом деле , 16 байтов

Этот ответ в значительной степени основан на ответе Jelly на jimmy23013 . Предложения по игре в гольф приветствуются! Попробуйте онлайн!

;;2╟┬Σ1(tZ`i<`Mm

Ungolfing

         Implicit input a.
;;       Duplicate a twice.
2╟       Wrap two of the duplicates into a list.
┬        Transpose the duplicates.
Σ        Sum all of the columns to get a flat list like this:
           [a_0, a_0, a_1, a_1, ..., a_n, a_n]
         This gets the parent nodes of the heap.
1(t      Get a[1:] using the remaining duplicate of a.
         This is a list of the child nodes of the heap.
Z`i<`M   Check if every child node is less than its parent node.
m        Get the minimum. This returns 1 if a is a max-heap, else 0.
         Implicit return.