Ein Heap , auch Prioritätswarteschlange genannt, ist ein abstrakter Datentyp. Konzeptionell handelt es sich um einen Binärbaum, bei dem die untergeordneten Elemente jedes Knotens kleiner oder gleich dem Knoten selbst sind. (Angenommen, es ist ein maximaler Heap.) Wenn ein Element verschoben oder verschoben wird, wird der Heap selbst neu angeordnet, sodass das größte Element das nächste ist, das verschoben wird. Es kann leicht als Baum oder als Array implementiert werden.

Wenn Sie dies akzeptieren möchten, müssen Sie feststellen, ob ein Array ein gültiger Heap ist. Ein Array hat die Form eines Heapspeichers, wenn die untergeordneten Elemente jedes Elements kleiner oder gleich dem Element selbst sind. Nehmen Sie das folgende Array als Beispiel:

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

In Wirklichkeit ist dies ein binärer Baum, der in Form eines Arrays angeordnet ist. Dies liegt daran, dass jedes Element Kinder hat. 90 hat zwei Kinder, 15 und 10.

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

15 hat auch Kinder, 7 und 12:

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

10 hat Kinder:

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

und das nächste Element wäre auch ein Kind von 10 Jahren, außer dass es keinen Platz gibt. 7, 12 und 2 hätten auch Kinder, wenn das Array lang genug wäre. Hier ist ein weiteres Beispiel für einen Haufen:

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

Und hier ist eine Visualisierung des Baums, den das vorherige Array erstellt:

Nur für den Fall, dass dies nicht klar genug ist, finden Sie hier die explizite Formel, um die untergeordneten Elemente des i'th-Elements abzurufen

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

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

Sie müssen ein nicht leeres Array als Eingabe verwenden und einen Wahrheitswert ausgeben, wenn sich das Array in der Heap-Reihenfolge befindet, andernfalls einen falschen Wert. Dies kann ein 0-indizierter Heap oder ein 1-indizierter Heap sein, solange Sie angeben, welches Format Ihr Programm / Ihre Funktion erwartet. Sie können davon ausgehen, dass alle Arrays nur positive ganze Zahlen enthalten. Sie können nicht alle heap-builtins verwenden. Dies schließt ein, ist aber nicht darauf beschränkt

• Funktionen, die bestimmen, ob ein Array in Heap-Form vorliegt
• Funktionen, die ein Array in einen Heap oder in eine Heap-Form konvertieren
• Funktionen, die ein Array als Eingabe nehmen und eine Heap-Datenstruktur zurückgeben

Mit diesem Python-Skript können Sie überprüfen, ob ein Array in Heap-Form vorliegt oder nicht (0 indiziert):

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:

Alle diese Eingaben sollten True zurückgeben:

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

Und all diese Eingaben sollten False zurückgeben:

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

Wie üblich ist dies Codegolf, daher gelten Standardlücken und die kürzeste Antwort in Bytes gewinnt!

Gelee, 11 9 5 Bytes

x2:ḊṂ

4 Bytes entfernt dank Dennis!

Probieren Sie es hier aus.

Erläuterung

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 Byte

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

Edit: Das Korrigieren meines Codes für die Spezifikationsklärung kostet 1 Byte, also danke an @ edc65 für die Einsparung von 4 Byte.

Haskell, 33 Bytes

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

oder

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

J, 24 Bytes

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

Erläuterung

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

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Ein Array ist wahr, wenn es nicht leer ist und alle seine Einträge ungleich Null sind. Sonst ist es falsch. Hier sind einige Beispiele .

Erläuterung

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)

Gibt 0 für Falsy und ungleich 0 für Truthy aus.

Überprüft, ob das letzte Element am Index kleiner oder gleich dem übergeordneten Element ist len(l)/2-1. Überprüfen Sie anschließend erneut, ob der Wert True ist, und entfernen Sie das letzte Element der Liste usw., bis die Liste leer ist.

48 Bytes:

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

Überprüft, ob idas Element an jedem Index höchstens das übergeordnete Element am Index ist (i-1)/2. Ist dies nicht der Fall, erzeugt die Flächenteilung 0.

Tun Sie das Basisgehäuse wie i/len(l)orergibt die gleiche Länge. Ich hatte zuerst versucht zu zippen, bekam aber einen längeren Code (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

Hoffentlich habe ich das richtig verstanden. Nun, um zu sehen, ob ich noch ein paar Bytes loswerden kann. Hat die Bindung aufgegeben und einen sapply eingefügt und 1-basierten Vektor richtig behandelt.

Als unbenannte Funktion implementiert

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

Mit einigen Testfällen

> 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~_:_\(;./:*

Ab 3 Bytes dank Dennis golfen.

Probieren Sie es hier aus.

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

Probieren Sie es online aus

Netzhaut , 51 Bytes

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

Probieren Sie es online!

Nimmt eine durch Leerzeichen getrennte Liste von Zahlen als Eingabe. Ausgänge 1/ 0für wahr / falsch

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

Muss cein Container sein, der .operator[](int)und .size()dergleichen stützt 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;
}

Könnte kleiner sein, wenn truthy = 0und falsy = 1erlaubt wären.

R, 72 Bytes

Ein etwas anderer Ansatz als die andere R-Antwort .

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)

Liest die Eingabe von stdin, erstellt einen Vektor aller Vergleichspaare, subtrahiert sie voneinander und prüft, ob das Ergebnis eine negative Zahl oder Null ist.

Erläuterung

Eingaben von stdin lesen:

x=scan();

Kreieren Sie unsere Paare. Wir erstellen Indizes von 1...N(wobei Ndie Länge von ist x) für die übergeordneten Knoten. Wir nehmen dies zweimal, da jeder Elternteil (maximal) zwei Kinder hat. Wir nehmen auch die Kinder,(1...N)*2 und (1...N)*2+1. Für Indizes, die länger als sind x, gibt R NA"nicht verfügbar" zurück. Zur Eingabe 90 15 10 7 12 2gibt uns dieser Code 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)]

In diesem Vektor von Paaren hat jedes Element seinen Partner in einem Abstand von N*2 Entfernung. Zum Beispiel befindet sich der Partner von Punkt 1 auf Position 12 (6 * 2). Wir verwenden diff, um die Differenz zwischen diesen Paaren zu berechnen, und geben lag=N*2an, um die Artikel mit ihren richtigen Partnern zu vergleichen. Alle Operationen an NAElementen kehren einfach zurück NA.

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

Abschließend prüfen wir, ob alle diese zurückgegebenen Werte kleiner sind als 1(dh, dass die erste Zahl, das übergeordnete Element, größer war als die zweite Zahl, das untergeordnete Element)NA Werte von der Berücksichtigung ausgeschlossen werden.

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

Tatsächlich 16 Bytes

Diese Antwort basiert größtenteils auf der Jelly-Antwort von jimmy23013 . Golfvorschläge willkommen! Probieren Sie es 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.