Sterty , znany również jako priorytetów kolejce, to abstrakcyjny typ danych. Koncepcyjnie jest to drzewo binarne, w którym dzieci każdego węzła są mniejsze lub równe samemu węzłowi. (Zakładając, że jest to maksymalny stos.) Kiedy element jest popychany lub pękany, sterty układają się ponownie, tak aby największy element był następny. Można go łatwo wdrożyć jako drzewo lub tablicę.

Wyzwaniem, jeśli zdecydujesz się je zaakceptować, jest ustalenie, czy tablica jest prawidłową stertą. Tablica ma postać sterty, jeśli elementy potomne każdego elementu są mniejsze lub równe samemu elementowi. Weź jako przykład następującą tablicę:

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

Naprawdę jest to drzewo binarne ułożone w formie tablicy. Jest tak, ponieważ każdy element ma dzieci. 90 ma dwoje dzieci, 15 i 10 lat.

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

15 ma również dzieci, 7 i 12:

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

10 ma dzieci:

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

a następnym elementem będzie również dziecko w wieku 10 lat, z tym wyjątkiem, że nie ma miejsca. 7, 12 i 2 również miałyby dzieci, jeśli tablica była wystarczająco długa. Oto inny przykład sterty:

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

A oto wizualizacja drzewa, którą tworzy poprzednia tablica:

Na wypadek, gdyby nie było to wystarczająco jasne, oto wyraźna formuła, aby uzyskać dzieci z i-tego elementu

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

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

Musisz przyjąć niepustą tablicę jako dane wejściowe i wyprowadzić prawdziwą wartość, jeśli tablica jest w kolejności stosu, a w przeciwnym razie wartość fałsz. Może to być sterta o indeksie 0 lub sterta o indeksie 1, o ile określisz, jakiego formatu oczekuje Twój program / funkcja. Możesz założyć, że wszystkie tablice będą zawierać tylko dodatnie liczby całkowite. Być może nie stosować żadnych sterty pomocy poleceń wbudowanych. Obejmuje to między innymi

• Funkcje określające, czy tablica ma postać sterty
• Funkcje przekształcające tablicę w stertę lub w formę sterty
• Funkcje, które przyjmują tablicę jako dane wejściowe i zwracają strukturę danych sterty

Możesz użyć tego skryptu python, aby sprawdzić, czy tablica jest w formie stosu, czy nie (0 indeksowanych):

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:

Wszystkie te dane wejściowe powinny zwracać wartość 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]

Wszystkie te dane wejściowe powinny zwracać wartość 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]

Jak zwykle jest to gra w golfa, więc obowiązują standardowe luki i wygrywa najkrótsza odpowiedź w bajtach!

Galareta, 11 9 5 bajtów

x2:ḊṂ

4 bajty usunięte dzięki Dennisowi!

Wypróbuj tutaj.

Wyjaśnienie

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 bajtów

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

Edycja: Naprawienie mojego kodu dla wyjaśnienia specyfikacji kosztowało 1 bajt, więc dzięki @ edc65 za oszczędność 4 bajtów.

Haskell, 33 bajty

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

lub

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

J, 24 bajty

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

Wyjaśnienie

*/@:<:]{~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 bajtów

ttf2/k)>~4L)

Wypróbuj online!Lub sprawdź wszystkie przypadki testowe .

Tablica jest prawdziwa, jeśli nie jest pusta, a wszystkie jej wpisy są niezerowe. W przeciwnym razie jest to fałsz. Tu są kilka przykładów .

Wyjaśnienie

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 bajtów

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

Wyjście 0 dla Falsy, niezerowe dla Truthy.

Sprawdza, czy ostatni element jest mniejszy lub równy swojemu rodzicowi przy indeksie len(l)/2-1. Następnie powtarza się, aby sprawdzić, czy to samo jest Prawdą, po usunięciu ostatniego elementu listy i tak dalej, aż lista będzie pusta.

48 bajtów:

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

Sprawdza, czy przy każdym indeksie ielement jest najwyżej nadrzędny w indeksie(i-1)/2 . Podział podłogi daje 0, jeśli tak nie jest.

Wykonanie skrzynki podstawowej i/len(l)ordaje taką samą długość. Na początku próbowałem spakować, ale dostałem dłuższy kod (57 bajtów).

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

R, 97 88 82 bajtów

Mam nadzieję, że dobrze to zrozumiałem. Teraz sprawdź, czy uda mi się pozbyć więcej bajtów. Porzuciłem wiązanie i włożyłem sapply i odpowiednio poradziliśmy sobie z wektorem 1.

Zaimplementowano jako funkcję bez nazwy

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

Z kilkoma przypadkami testowymi

> 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 bajtów

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

Grał w golfa z 3 bajtami dzięki Dennisowi.

Wypróbuj tutaj.

Pyth, 8 bajtów

.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

Wypróbuj online

Siatkówka , 51 bajtów

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

Wypróbuj online!

Pobiera na wejściu listę liczb oddzieloną spacjami. Wyjścia 1/ 0dla prawdy / fałszu

C ++ 14, 134 105 bajtów

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

Wymaga cbycia pojemnikiem podtrzymującym .operator[](int)i tym .size()podobnym std::vector<int>.

Nie golfowany:

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

Może być mniejszy, jeśli dozwolone są wartości true = 0i falsy = 1.

R, 72 bajty

Nieco inne podejście od drugiej R odpowiedź .

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)

Odczytuje dane wejściowe ze standardowego wejścia, tworzy wektor wszystkich par porównania, odejmuje je od siebie i sprawdza, czy wynikiem jest liczba ujemna lub zero.

Wyjaśnienie

Czytaj dane wejściowe ze standardowego wejścia:

x=scan();

Stwórz nasze pary. Tworzymy indeksy 1...N(gdzie Njest długość x) dla węzłów nadrzędnych. Bierzemy to dwa razy, ponieważ każdy rodzic ma (maksymalnie) dwoje dzieci. Bierzemy również dzieci (1...N)*2i (1...N)*2+1. W przypadku wskaźników przekraczających długość xR zwraca NA„niedostępne”. Do wprowadzenia 90 15 10 7 12 2ten kod daje nam 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)]

W tym wektorze par każdy element ma swojego partnera w pewnej odległości N*2. Na przykład partner pozycji 1 znajduje się na pozycji 12 (6 * 2). Używamy diffdo obliczania różnicy między tymi parami, określając, lag=N*2aby porównać elementy z ich właściwymi partnerami. Wszelkie operacje na NAelementach po prostu zwracają NA.

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

Na koniec sprawdzamy, czy wszystkie te zwrócone wartości są mniejsze niż 1(tj. Czy pierwsza liczba, rodzic, była większa niż druga liczba, dziecko), wyłączając NAwartości z rozważania.

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

Właściwie 16 bajtów

Ta odpowiedź jest w dużej mierze oparta na odpowiedzi Jelly na jimmy23013 . Zapraszamy do gry w golfa! Wypróbuj 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.