Sebuah tumpukan , juga dikenal sebagai prioritas-antrian, adalah jenis data abstrak. Secara konseptual, itu adalah pohon biner di mana anak-anak dari setiap simpul lebih kecil dari atau sama dengan simpul itu sendiri. (Dengan asumsi itu adalah heap-max.) Ketika sebuah elemen didorong atau muncul, heap mengatur ulang dirinya sendiri sehingga elemen terbesar adalah yang berikutnya muncul. Ini dapat dengan mudah diimplementasikan sebagai pohon atau sebagai array

Tantangan Anda, jika Anda memilih untuk menerimanya, adalah menentukan apakah array adalah tumpukan yang valid. Array dalam bentuk heap jika anak-anak setiap elemen lebih kecil dari atau sama dengan elemen itu sendiri. Ambil array berikut sebagai contoh:

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

Sungguh, ini adalah pohon biner yang disusun dalam bentuk array. Ini karena setiap elemen punya anak. 90 memiliki dua anak, 15 dan 10.

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

15 juga memiliki anak, 7 dan 12:

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

10 memiliki anak:

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

dan elemen berikutnya juga akan menjadi anak 10, kecuali bahwa tidak ada ruang. 7, 12 dan 2 semuanya juga akan memiliki anak jika array cukup panjang. Berikut ini contoh lain dari heap:

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

Dan di sini adalah visualisasi pohon yang dibuat oleh array sebelumnya:

Kalau-kalau ini tidak cukup jelas, berikut adalah rumus eksplisit untuk mendapatkan anak-anak dari elemen ke-i

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

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

Anda harus mengambil array yang tidak kosong sebagai input dan output nilai kebenaran jika array berada di urutan tumpukan, dan nilai yang salah sebaliknya. Ini bisa berupa tumpukan berindeks 0, atau tumpukan berindeks 1 selama Anda menentukan format program / fungsi yang Anda harapkan. Anda dapat mengasumsikan bahwa semua array hanya akan mengandung bilangan bulat positif. Anda tidak boleh menggunakan heap-builtin. Ini termasuk, tetapi tidak terbatas pada

• Fungsi yang menentukan apakah array dalam bentuk heap
• Fungsi yang mengubah array menjadi heap atau menjadi heap-form
• Fungsi yang mengambil array sebagai input dan mengembalikan struktur data tumpukan

Anda dapat menggunakan skrip python ini untuk memverifikasi apakah array dalam bentuk heap atau tidak (0 diindeks):

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

Tes IO:

Semua input ini harus mengembalikan 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]

Dan semua input ini harus mengembalikan 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]

Seperti biasa, ini adalah kode-golf, sehingga celah standar berlaku dan jawaban terpendek dalam byte menang!

Jeli, 11 9 5 byte

x2:ḊṂ

4 byte dihapus berkat Dennis!

Coba di sini.

Penjelasan

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

Sunting: Memperbaiki kode saya untuk biaya klarifikasi spesifikasi 1 byte, jadi terima kasih kepada @ edc65 karena menghemat 4 byte.

Haskell, 33 byte

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

atau

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

J, 24 byte

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

Penjelasan

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

ttf2/k)>~4L)

Cobalah online! Atau verifikasi semua kasus uji .

Array benar jika tidak kosong dan semua entri adalah nol. Kalau tidak, itu palsu. Berikut ini beberapa contohnya .

Penjelasan

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 byte

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

Output 0 untuk Falsy, bukan nol untuk Truthy.

Periksa bahwa elemen terakhir kurang dari atau sama dengan induknya di indeks len(l)/2-1. Kemudian, berulang untuk memeriksa bahwa hal yang sama adalah Benar dengan elemen terakhir dari daftar dihapus, dan seterusnya hingga daftar kosong.

48 byte:

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

Cek di setiap indeks i , elemen paling banyak adalah induknya di indeks (i-1)/2. Divisi lantai menghasilkan 0 jika ini bukan masalahnya.

Melakukan casing dasar karena i/len(l)ormemberikan panjang yang sama. Saya telah mencoba zip pada awalnya, tetapi mendapat kode yang lebih panjang (57 byte).

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

R, 97 88 82 byte

Semoga saya mengerti ini dengan benar. Sekarang untuk melihat apakah saya bisa menghilangkan beberapa byte lagi. Membuang rbind dan memasukkan sapply dan menangani vektor berbasis 1 dengan benar.

Diimplementasikan sebagai fungsi yang tidak disebutkan namanya

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

Dengan beberapa kasus uji

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

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

Golf 3 byte berkat Dennis.

Coba di sini.

Pyth, 8 byte

.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

Cobalah online

Retina , 51 byte

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

Cobalah online!

Mengambil daftar angka yang dipisahkan ruang sebagai input. Keluaran 1/ 0untuk kebenaran / salah

C ++ 14, 134 105 byte

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

Perlu cmenjadi wadah pendukung .operator[](int)dan .size(), seperti std::vector<int>.

Tidak Disatukan:

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

Bisa lebih kecil jika truthy = 0dan falsy = 1diizinkan.

R, 72 byte

Pendekatan yang sedikit berbeda dari jawaban R lainnya .

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)

Membaca input dari stdin, membuat vektor semua pasangan pembanding, menguranginya satu sama lain, dan memeriksa bahwa hasilnya adalah angka negatif atau nol.

Penjelasan

Baca input dari stdin:

x=scan();

Buat pasangan kami. Kami membuat indeks 1...N(di mana Npanjangnya x) untuk node induk. Kami mengambil ini dua kali karena setiap orang tua memiliki (maksimal) dua anak. Kami juga membawa anak-anak, (1...N)*2dan (1...N)*2+1. Untuk indeks yang melebihi panjang x, R mengembalikan NA, 'tidak tersedia'. Untuk input 90 15 10 7 12 2, kode ini memberi kita 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)]

Dalam vektor pasangan ini, setiap elemen memiliki pasangannya pada jarak yang N*2jauh. Misalnya, mitra item 1 terletak di posisi 12 (6 * 2). Kami menggunakan diffuntuk menghitung perbedaan antara pasangan ini, menentukan lag=N*2untuk membandingkan item dengan mitra yang benar. Operasi apa pun pada NAelemen cukup kembali NA.

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

Akhirnya, kami memeriksa bahwa semua nilai yang dikembalikan ini kurang dari 1(yaitu bahwa angka pertama, orang tua, lebih besar dari angka kedua, anak), tidak termasuk NAnilai dari pertimbangan.

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

Sebenarnya , 16 byte

Jawaban ini sebagian besar didasarkan pada jawaban Jelly jimmy23013 . Selamat datang saran bermain golf! Cobalah online!

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

Tidak melakukanolf

         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.