Um heap , também conhecido como fila de prioridade, é um tipo de dados abstrato. Conceitualmente, é uma árvore binária em que os filhos de cada nó são menores ou iguais ao próprio nó. (Supondo que seja um heap máximo.) Quando um elemento é pressionado ou populado, o heap se reorganiza para que o elemento maior seja o próximo a ser popped. Pode ser facilmente implementado como uma árvore ou como uma matriz.

Seu desafio, se você optar por aceitá-lo, é determinar se uma matriz é uma pilha válida. Uma matriz está no formato heap se os filhos de cada elemento forem menores ou iguais ao próprio elemento. Tome a seguinte matriz como exemplo:

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

Realmente, essa é uma árvore binária organizada na forma de uma matriz. Isso ocorre porque todo elemento tem filhos. 90 tem dois filhos, 15 e 10.

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

15 também tem filhos, 7 e 12:

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

10 tem filhos:

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

e o próximo elemento também seria um filho de 10 anos, exceto que não há espaço. 7, 12 e 2 também teriam filhos se a matriz fosse longa o suficiente. Aqui está outro exemplo de pilha:

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

E aqui está uma visualização da árvore que a matriz anterior faz:

Caso isso não esteja claro o suficiente, aqui está a fórmula explícita para obter os filhos do i-ésimo elemento

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

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

Você deve usar uma matriz não vazia como entrada e gerar um valor verdadeiro se a matriz estiver na ordem da pilha e, caso contrário, um valor falso. Pode ser um heap indexado 0 ou um heap indexado 1, desde que você especifique qual formato seu programa / função espera. Você pode assumir que todas as matrizes conterão apenas números inteiros positivos. Você não pode usar nenhum heap-builtins. Isso inclui, mas não está limitado a

• Funções que determinam se uma matriz está no formato heap
• Funções que convertem uma matriz em uma pilha ou em forma de pilha
• Funções que tomam uma matriz como entrada e retornam uma estrutura de dados de heap

Você pode usar este script python para verificar se uma matriz está no formato heap ou não (0 indexado):

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

Teste de E / S:

Todas essas entradas devem retornar 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]

E todas essas entradas devem retornar 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]

Como de costume, isso é código-golfe, então as brechas padrão se aplicam e a resposta mais curta em bytes vence!

Geléia, 11 9 5 bytes

x2:ḊṂ

4 bytes removidos graças a Dennis!

Experimente aqui.

Explicação

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 bytes

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

Edit: A correção do meu código para o esclarecimento das especificações custa 1 byte, por isso, obrigado a @ edc65 por economizar 4 bytes.

Haskell, 33 bytes

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

ou

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

J, 24 bytes

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

Explicação

*/@:<:]{~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 bytes

ttf2/k)>~4L)

Experimente online! Ou verifique todos os casos de teste .

Uma matriz é verdadeira se não estiver vazia e todas as suas entradas forem diferentes de zero. Caso contrário, é falso. Aqui estão alguns exemplos .

Explicação

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 bytes

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

Saídas 0 para Falsy, diferente de zero para Truthy.

Verifica se o último elemento é menor ou igual ao seu pai no índice len(l)/2-1. Em seguida, é repetido para verificar se o mesmo é True com o último elemento da lista removido e assim por diante até que a lista esteja vazia.

48 bytes:

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

Verifica se, em cada índice i, o elemento é no máximo seu pai no índice (i-1)/2. A divisão de piso produz 0 se esse não for o caso.

Fazendo o estojo de base, i/len(l)ordá o mesmo comprimento. Eu tentei compactar no começo, mas obtive um código mais longo (57 bytes).

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

R, 97 88 82 bytes

Espero ter entendido isso corretamente. Agora, para ver se consigo me livrar de mais alguns bytes. Abandonei o rbind e coloquei um sapply e lide adequadamente com o vetor baseado em 1.

Implementado como uma função sem nome

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

Com alguns dos casos de teste

> 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 bytes

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

Golpeou 3 bytes graças a Dennis.

Experimente aqui.

Pitão, 8 bytes

.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

Experimente online

Retina , 51 bytes

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

Experimente online!

Leva uma lista de números separados por espaço como entrada. Saídas 1/ 0para verdade / false

C ++ 14, 134 105 bytes

#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));}

Requer cser um contêiner suportando .operator[](int)e .size(), como 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;
}

Pode ser menor se truthy = 0e falsy = 1forem permitidos.

R, 72 bytes

Uma abordagem ligeiramente diferente da outro resposta 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)

Lê a entrada do stdin, cria um vetor de todos os pares de comparação, subtrai-os um do outro e verifica se o resultado é um número negativo ou zero.

Explicação

Leia a entrada do stdin:

x=scan();

Crie nossos pares. Criamos índices de 1...N(onde Né o comprimento de x) para os nós principais. Tomamos isso duas vezes, pois cada pai ou mãe tem (no máximo) dois filhos. Também levamos as crianças (1...N)*2e (1...N)*2+1. Para índices além do comprimento de x, R retorna NA, 'não disponível'. Para entrada 90 15 10 7 12 2, esse código nos fornece90 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)]

Neste vetor de pares, cada elemento tem seu parceiro a uma distância N*2distante. Por exemplo, o parceiro do item 1 está localizado na posição 12 (6 * 2). Usamos diffpara calcular a diferença entre esses pares, especificando lag=N*2para comparar os itens com seus parceiros corretos. Quaisquer operações nos NAelementos simplesmente retornam NA.

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

Por fim, verificamos que todos esses valores retornados são menores que 1(ou seja, que o primeiro número, o pai, seja maior que o segundo número, o filho), excluindo NAvalores da consideração.

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

Na realidade , 16 bytes

Esta resposta é baseada principalmente na resposta de jimmy23013 Jelly . Sugestões de golfe são bem-vindas! Experimente online!

;;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.