Medianı tapın - 2#4074

Medianı tapın - 2 (Həll təhlili)

Məsələnin həllini xətti massiv vasitəsilə modelləşdirək. Hər addımda daxil olan ədədləri onun içində sıralanmış şəkildə saxlayacağıq. Yeni elementin daxil ediləcəyi mövqeyi ikili axtarış vasitəsilə tapacağıq. Lakin daxiletmə əməliyyatının özü (məsələn, massiv $v ec t or$ verilənlər strukturu ilə həyata keçirilibsə) xətti zamanda yerinə yetirilir. Beləliklə, $O (n^{2})$ O(n^2) zaman mürəkkəbliyinə malik ümumi həll vaxt məhdudiyyətinə sığmayacaq.

İki qalaq (heap) elan edək: biri — minimumu saxlamaq üçün ( $min$ -qalaq), digəri — maksimumu saxlamaq üçün ( $ma x$ -qalaq). Onların işini elə təşkil edək ki, aşağıdakı şərtlər ödənsin:

$ma x$ -qalağın istənilən elementi $min$ -qalağın istənilən elementindən kiçik olsun (kiçik ədədlər $ma x$ -qalaqda, böyük ədədlər isə $min$ -qalaqda saxlanılır);
qalaqların ölçüləri bərabər olsun. Əgər ümumi element sayı tək olarsa, $min$ -qalaq $ma x$ -qalaqdan bir element çox saxlamalıdır.

Yeni element əlavə edildikdə, əgər o, $min$ -qalağın minimal elementindən kiçik deyilsə, onu $min$ -qalağa yerləşdiririk; əks halda — $ma x$ -qalağa. Bundan sonra yuxarıda qeyd olunan xüsusiyyətləri qorumaq üçün qalaqların balanslaşdırılmasını yerinə yetiririk:

Əgər $ma x$ -qalağın ölçüsü $min$ -qalağın ölçüsündən böyükdürsə, $ma x$ -qalağın ən böyük elementini $min$ -qalağa köçürürük.
Əgər $min$ -qalağın ölçüsü $ma x$ -qalağın ölçüsündən birdən çox böyükdürsə, $min$ -qalağın ən kiçik elementini $ma x$ -qalağa köçürürük.

Cari ardıcıllığın medianı aşağıdakı kimi müəyyən edilir:

əgər ədədlərin sayı tək olarsa, medianı $min$ -qalağın ən kiçik elementi təşkil edir;
əgər ədədlərin sayı cüt olarsa, median $min$ -qalağın ən kiçik elementi ilə $ma x$ -qalağın ən böyük elementinin ədədi ortasına bərabərdir.

Elementin qalağa daxil edilməsi və sonrakı balanslaşdırma $O (l o g_{2} n)$ O(log_2n) vaxtında yerinə yetirilir. Beləliklə, alqoritmin ümumi işləmə vaxtı $O (n l o g_{2} n)$ O(nlog_2n) təşkil edir.

Misal

Ədədlərin ardıcıl daxil olması zamanı medianın hesablanması prosesinə baxaq. Aydınlıq üçün hər yeni ədəd əlavə edildikdən sonra ardıcıllığın nizamlandığını qəbul edəcəyik. Hər ardıcıllığın altında ona uyğun median dəyəri göstərilib.

Misaldakı bütün elementlər emal edildikdən sonra qalaqların vəziyyəti aşağıdakı kimi olacaq:

Elementlərin sayı tək olduğundan, median $min$ -qalağın ən kiçik elementinə, yəni $4$ -ə bərabərdir.

Tutaq ki, növbəti daxil olan ədəd $35$ -dir. O, $min$ -qalağın minimal elementindən kiçik olmadığı üçün onu $min$ -qalağa əlavə edirik. Bundan sonra $min$ -qalağın ölçüsü $ma x$ -qalağın ölçüsündən iki element çox olacaq, buna görə də balanslaşdırma yerinə yetirilməlidir: $min$ -qalağın ən kiçik elementini ( $4$ ) $ma x$ -qalağa köçürürük. Başqa sözlə, $4$ -ü $min$ -qalaqdan silib $ma x$ -qalağa əlavə edirik.

İndi massivdəki elementlərin ümumi sayı cüt olduğundan, median $min$ -qalağın ən kiçik elementinin ( $35$ ) və $ma x$ -qalağın ən böyük elementinin ( $4$ ) ədədi ortası kimi müəyyən edilir, yəni $(35 + 4) /2 = 19$ (35 + 4) / 2 = 19. Məsələdə medianın yalnız tam hissəsini çıxarmaq tələb olunur.

Alqoritmin realizasiyası

$min$ -qalağı $m M in H e a p$ mMinHeap və $ma x$ -qalağı $m M a x H e a p$ mMaxHeap elan edək.

priority_queue<int, vector<int>, greater<int> > mMinHeap;
priority_queue<int, vector<int>, less<int> > mMaxHeap;

Qalaqları ilkin qiymətləndirək. $c$ dəyişənində daxil olan ədədlərin sayını saxlayacağıq. Rahatlıq üçün qalaqları fiktiv elementlərlə ilkin qiymətləndiririk.

mMaxHeap.push(-MAX); mMinHeap.push(MAX);
c = 1;

Növbəti ədədi emal edirik.

while(scanf("%d",&n) == 1) 
{

$n$ -in dəyərindən asılı olaraq onu qalaqlardan birinə yerləşdiririk.

  if (n >= mMinHeap.top()) mMinHeap.push(n);
  else mMaxHeap.push(n);

Əgər $ma x$ -qalağın ölçüsü $min$ -qalağın ölçüsündən böyükdürsə və ya $min$ -qalağın ölçüsü $ma x$ -qalağın ölçüsündən birdən çox böyükdürsə, balanslaşdırma yerinə yetiririk.

  if(mMaxHeap.size() > mMinHeap.size())
  {

$ma x$ -qalağın ən böyük elementini $min$ -qalağa köçürürük.

    mMinHeap.push(mMaxHeap.top());
    mMaxHeap.pop();
  } else

  if(mMaxHeap.size() + 1 < mMinHeap.size())
  {

$min$ -qalağın ən kiçik elementini $ma x$ -qalağa köçürürük.

    mMaxHeap.push(mMinHeap.top());
    mMinHeap.pop();
  }

Massivdəki elementlərin sayının cüt-təkliyindən asılı olaraq medianın dəyərini çap edirik.

  if (c % 2) printf("%d\n",mMinHeap.top()); 
  else printf("%d\n",(mMinHeap.top() + mMaxHeap.top())/2); 
  c++;
}