Elemanları tamsayılardan oluşan n elemanlı bir A[1..n] dizisi, eğer her i ∈ {1, 2, …, ⌊n/2⌋} indisi için A[i] ≤ A[2i] ve (2i + 1 ≤ n iken) A[i] ≤ A[2i + 1] şartlarını sağlıyorsa yığın olarak adlandırılır. Bu şartları sağlamayan diziler yığın değildir.

Yığın olduğu bilinen 500 elemanlı bir dizide en küçük elemanı bulmak için en az kaç karşılaştırma gereklidir?

Yığın olduğu bilinen 250 elemanlı bir dizide en büyük elemanı bulmak için en az kaç karşılaştırma gereklidir?

Aşağıdaki mantıksal önermelerden hangileri doğrudur?

(I) Yığın olmayan herhangi bir dizi elemanlarının yerleri değiştirilerek yığın haline getirilebilir.

(II) 50 farklı tamsayı içeren 50 elemanlı bir diziden en fazla 50 adet farklı yığın oluşturulabilir.

(III) A[1..n] dizisi bir yığın ise bunun bir alt dizisi olan A[2..n − 1] dizisi de bir yığındır.

n elemanlı bir A yığını ve bir p tamsayısı verilmiştir. Sizden istenen bu yığının k. (1 ≤ k ≤ n) en küçük elemanının p’den daha küçük olup olmadığını belirlemektir. Bu problem için zaman karmaşıklığı en az hangisidir?