Un tas , également appelé file d'attente prioritaire, est un type de données abstrait. Conceptuellement, c'est un arbre binaire où les enfants de chaque nœud sont inférieurs ou égaux au nœud lui-même. (En supposant qu'il s'agit d'un tas max.) Lorsqu'un élément est poussé ou sauté, le tas se réorganise de sorte que le plus grand élément soit le prochain à sauter. Il peut facilement être implémenté sous forme d'arbre ou de tableau.

Votre défi, si vous choisissez de l'accepter, est de déterminer si un tableau est un tas valide. Un tableau est sous forme de tas si les enfants de chaque élément sont inférieurs ou égaux à l'élément lui-même. Prenons l'exemple du tableau suivant:

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

En réalité, il s'agit d'un arbre binaire disposé sous la forme d'un tableau. C'est parce que chaque élément a des enfants. 90 a deux enfants, 15 et 10 ans.

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

15 a également des enfants, 7 et 12 ans:

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

10 a des enfants:

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

et l'élément suivant serait également un enfant de 10 ans, sauf qu'il n'y a pas de place. 7, 12 et 2 auraient tous aussi des enfants si la matrice était suffisamment longue. Voici un autre exemple de tas:

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

Et voici une visualisation de l'arbre que fait le tableau précédent:

Juste au cas où ce ne serait pas assez clair, voici la formule explicite pour obtenir les enfants du ième élément

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

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

Vous devez prendre un tableau non vide en entrée et générer une valeur véridique si le tableau est dans l'ordre du segment de mémoire et une valeur fausse dans le cas contraire. Cela peut être un tas indexé 0 ou un tas indexé 1 tant que vous spécifiez le format que votre programme / fonction attend. Vous pouvez supposer que tous les tableaux ne contiendront que des entiers positifs. Vous ne pouvez pas utiliser de commandes intégrées au tas. Cela comprend, mais sans s'y limiter

• Fonctions qui déterminent si un tableau est sous forme de segment de mémoire
• Fonctions qui convertissent un tableau en tas ou en forme de tas
• Fonctions qui prennent un tableau en entrée et retournent une structure de données de tas

Vous pouvez utiliser ce script python pour vérifier si un tableau est en forme de tas ou non (0 indexé):

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

Test IO:

Toutes ces entrées doivent renvoyer 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]

Et toutes ces entrées doivent retourner 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]

Comme d'habitude, il s'agit de code-golf, donc les failles standard s'appliquent et la réponse la plus courte en octets gagne!

Gelée, 11 9 5 octets

x2:ḊṂ

4 octets supprimés grâce à Dennis!

Essayez-le ici.

Explication

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 octets

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

Edit: La correction de mon code pour la clarification des spécifications coûte 1 octet, donc merci à @ edc65 pour avoir économisé 4 octets.

Haskell, 33 octets

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

ou

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

J, 24 octets

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

Explication

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

ttf2/k)>~4L)

Essayez-le en ligne!Ou vérifiez tous les cas de test .

Un tableau est vrai s'il n'est pas vide et que toutes ses entrées sont différentes de zéro. Sinon, c'est faux. Voici quelques exemples .

Explication

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 octets

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

Sorties 0 pour Falsy, non nul pour Truthy.

Vérifie que le dernier élément est inférieur ou égal à son parent à l'index len(l)/2-1. Ensuite, revient pour vérifier qu'il en est de même avec le dernier élément de la liste supprimé, et ainsi de suite jusqu'à ce que la liste soit vide.

48 octets:

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

Vérifie qu'à chaque index i, l'élément est tout au plus son parent à l'index(i-1)/2 . La division au sol produit 0 si ce n'est pas le cas.

Faire le cas de base comme i/len(l)ordonne la même longueur. J'avais essayé de zipper au début, mais j'ai obtenu un code plus long (57 octets).

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

R, 97 88 82 octets

J'espère que j'ai bien compris cela. Voyons maintenant si je peux me débarrasser de quelques octets supplémentaires. Abandonné le rbind et mis dans un sapply et traiter correctement le vecteur basé sur 1.

Implémenté en tant que fonction sans nom

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

Avec quelques cas de test

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

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

Golfé 3 octets grâce à Dennis.

Essayez-le ici.

Pyth, 8 octets

.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

Essayez-le en ligne

Rétine , 51 octets

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

Essayez-le en ligne!

Prend une liste de nombres séparés par des espaces comme entrée. Sorties 1/ 0pour véridique / faux

C ++ 14, 134 105 octets

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

Exige cd'être un conteneur supportant .operator[](int)et .size(), comme std::vector<int>.

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

Pourrait être plus petit si truey = 0et falsy = 1étaient autorisés.

R, 72 octets

Une approche légèrement différente de l'autre réponse 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)

Lit l'entrée de stdin, crée un vecteur de toutes les paires de comparaison, les soustrait les unes des autres et vérifie que le résultat est un nombre négatif ou zéro.

Explication

Lire l'entrée de stdin:

x=scan();

Créez nos paires. Nous créons des indices de 1...N(où Nest la longueur de x) pour les nœuds parents. Nous prenons cela deux fois car chaque parent a (au maximum) deux enfants. Nous emmenons aussi les enfants, (1...N)*2et (1...N)*2+1. Pour les indices au-delà de la longueur de x, R renvoie NA«non disponible». Pour la saisie 90 15 10 7 12 2, ce code nous donne 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)]

Dans ce vecteur de paires, chaque élément a son partenaire à distance N*2. Par exemple, le partenaire de l'article 1 est situé à la position 12 (6 * 2). Nous utilisons diffpour calculer la différence entre ces paires, en spécifiant lag=N*2de comparer les articles à leurs bons partenaires. Toutes les opérations sur les NAéléments reviennent simplement NA.

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

Enfin, nous vérifions que toutes ces valeurs retournées sont inférieures à 1(c'est-à-dire que le premier nombre, le parent, était plus grand que le deuxième nombre, l'enfant), excluant les NAvaleurs de la considération.

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

Réellement , 16 octets

Cette réponse est largement basée sur la réponse Jelly de jimmy23013 . Suggestions de golf bienvenues! Essayez-le en ligne!

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