Un montón , también conocido como cola prioritaria, es un tipo de datos abstracto. Conceptualmente, es un árbol binario donde los hijos de cada nodo son más pequeños o iguales al nodo en sí. (Suponiendo que se trata de un montón máximo). Cuando se empuja o hace estallar un elemento, el montón se reorganiza, de modo que el elemento más grande es el siguiente en aparecer. Se puede implementar fácilmente como un árbol o como una matriz.

Su desafío, si elige aceptarlo, es determinar si una matriz es un montón válido. Una matriz está en forma de montón si los elementos secundarios de cada elemento son más pequeños o iguales que el elemento mismo. Tome la siguiente matriz como ejemplo:

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

Realmente, este es un árbol binario dispuesto en forma de matriz. Esto se debe a que cada elemento tiene hijos. 90 tiene dos hijos, 15 y 10.

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

15 también tiene hijos, 7 y 12:

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

10 tiene hijos:

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

y el siguiente elemento también sería un niño de 10 años, excepto que no hay espacio. 7, 12 y 2 también tendrían hijos si la matriz fuera lo suficientemente larga. Aquí hay otro ejemplo de un montón:

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

Y aquí hay una visualización del árbol que hace la matriz anterior:

En caso de que esto no sea lo suficientemente claro, aquí está la fórmula explícita para obtener los elementos secundarios del elemento i

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

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

Debe tomar una matriz no vacía como entrada y salida de un valor verdadero si la matriz está en orden de almacenamiento dinámico, y un valor falso de lo contrario. Esto puede ser un montón indexado 0 o un montón indexado 1 siempre que especifique qué formato espera su programa / función. Puede suponer que todas las matrices solo contendrán enteros positivos. Puedes no se utilice ningún heap-órdenes internas. Esto incluye, pero no se limita a

• Funciones que determinan si una matriz está en forma de montón
• Funciones que convierten una matriz en un montón o en forma de montón
• Funciones que toman una matriz como entrada y devuelven una estructura de datos de montón

Puede usar este script de Python para verificar si una matriz está en forma de montón o no (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

Prueba IO:

Todas estas entradas deberían devolver 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]

Y todas estas entradas deberían devolver 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 costumbre, este es el código de golf, por lo que se aplican las lagunas estándar y gana la respuesta más corta en bytes.

Jalea, 11 9 9 5 bytes

x2:ḊṂ

¡4 bytes eliminados gracias a Dennis!

Pruébalo aquí.

Explicación

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])

Editar: arreglar mi código para la aclaración de especificaciones costó 1 byte, así que gracias a @ edc65 por guardar 4 bytes.

Haskell, 33 bytes

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

o

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

J, 24 bytes

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

Explicación

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

Pruébalo en línea! O verificar todos los casos de prueba .

Una matriz es verdadera si no está vacía y todas sus entradas son distintas de cero. De lo contrario, es falso. Aquí hay algunos ejemplos. .

Explicación

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)

Salidas 0 para Falsy, distintas de cero para Truthy.

Comprueba que el último elemento es menor o igual que su padre en el índice len(l)/2-1. Luego, vuelve a comprobar que lo mismo es Verdadero con el último elemento de la lista eliminado, y así sucesivamente hasta que la lista esté vacía.

48 bytes:

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

Comprueba que en cada índice i, el elemento es como máximo su padre en el índice (i-1)/2. La división de piso produce 0 si este no es el caso.

Hacer el caso base como i/len(l)orda la misma longitud. Al principio intenté comprimir, pero obtuve un código más largo (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 haber entendido esto correctamente. Ahora para ver si puedo deshacerme de algunos bytes más. Eliminó el rbind y colocó una muestra y lidió con el vector basado en 1 correctamente.

Implementado como una función sin nombre

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

Con algunos de los casos de prueba.

> 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 dieciséis 13 12 bytes

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

Golfed 3 bytes gracias a Dennis.

Pruébalo aquí.

Pyth, 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

Pruébalo en línea

Retina , 51 bytes

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

Pruébalo en línea!

Toma una lista de números separados por espacios como entrada. Salidas 1/ 0para verdad / falso

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

Requiere cser un contenedor de soporte .operator[](int)y .size(), como std::vector<int>.

Sin golf:

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

Podría ser más pequeño si se permitiera la verdad = 0y la falsedad = 1.

R, 72 bytes

Un enfoque ligeramente diferente de la otra respuesta 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)

Lee la entrada de stdin, crea un vector de todos los pares de comparación, los resta entre sí y verifica que el resultado sea un número negativo o cero.

Explicación

Leer la entrada de stdin:

x=scan();

Crea nuestras parejas. Creamos índices de 1...N(donde Nes la longitud de x) para los nodos principales. Tomamos esto dos veces ya que cada padre tiene (como máximo) dos hijos. También tomamos a los niños, (1...N)*2y (1...N)*2+1. Para índices más allá de la longitud de x, R devuelve NA, 'no disponible'. Para la entrada 90 15 10 7 12 2, este código nos da 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)]

En este vector de pares, cada elemento tiene su compañero a una distancia de N*2distancia. Por ejemplo, el compañero del elemento 1 se encuentra en la posición 12 (6 * 2). Usamos diffpara calcular la diferencia entre estos pares, especificando lag=N*2para comparar los artículos con sus socios correctos. Cualquier operación en NAelementos simplemente regresa NA.

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

Finalmente, verificamos que todos estos valores devueltos sean menores que 1(es decir, que el primer número, el padre, era mayor que el segundo número, el hijo), excluyendo los NAvalores de la consideración.

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

En realidad , 16 bytes

Esta respuesta se basa en gran medida en la respuesta Jelly de jimmy23013 . Sugerencias de golf bienvenidas! Pruébalo en línea!

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

No golfista

         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.