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!
[3, 2, 1, 1]
?Odpowiedzi:
Galareta,
1195 bajtów4 bajty usunięte dzięki Dennisowi!
Wypróbuj tutaj.
Wyjaśnienie
źródło
JavaScript (ES6),
3430 bajtówEdycja: Naprawienie mojego kodu dla wyjaśnienia specyfikacji kosztowało 1 bajt, więc dzięki @ edc65 za oszczędność 4 bajtów.
źródło
[93, 15, 87, 7, 15, 5]
i 6[5, 5, 5, 5, 5, 5, 5, 5]
a=>!a.some((e,i)=>e>a[i-1>>1])
Haskell, 33 bajty
lub
źródło
J, 24 bajty
Wyjaśnienie
źródło
MATL ,
1312 bajtówWypró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
źródło
Python 2, 45 bajtów
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:
Sprawdza, czy przy każdym indeksie
i
element 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)or
daje taką samą długość. Na początku próbowałem spakować, ale dostałem dłuższy kod (57 bajtów).źródło
R,
97 8882 bajtówMam 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
Z kilkoma przypadkami testowymi
źródło
seq(Y)
zamiast1:length(Y)
.CJam,
19161312 bajtówGrał w golfa z 3 bajtami dzięki Dennisowi.
Wypróbuj tutaj.
źródło
Pyth, 8 bajtów
Wypróbuj online
źródło
Siatkówka , 51 bajtów
Wypróbuj online!
Pobiera na wejściu listę liczb oddzieloną spacjami. Wyjścia
1
/0
dla prawdy / fałszuźródło
C ++ 14,
134105 bajtówWymaga
c
bycia pojemnikiem podtrzymującym.operator[](int)
i tym.size()
podobnymstd::vector<int>
.Nie golfowany:
Może być mniejszy, jeśli dozwolone są wartości true =
0
i falsy =1
.źródło
R, 72 bajty
Nieco inne podejście od drugiej R odpowiedź .
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:
Stwórz nasze pary. Tworzymy indeksy
1...N
(gdzieN
jest 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)*2
i(1...N)*2+1
. W przypadku wskaźników przekraczających długośćx
R zwracaNA
„niedostępne”. Do wprowadzenia90 15 10 7 12 2
ten kod daje nam90 15 10 7 12 2 90 15 10 7 12 2 15 7 2 NA NA NA 10 12 NA NA NA NA
.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żywamydiff
do obliczania różnicy między tymi parami, określając,lag=N*2
aby porównać elementy z ich właściwymi partnerami. Wszelkie operacje naNA
elementach po prostu zwracająNA
.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ącNA
wartości z rozważania.źródło
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!
Ungolfing
źródło