Max-qalaq#10166

Max-qalaq (Həll təhlili)

Giriş məlumatlarını $a$ massivində saxlayaq. Massivin $n /2$ -dən $1$ -ə qədər olan bütün indeksləri üçün ardıcıl olaraq heapify prosedurunu tətbiq edək. Nəticədə massiv max-qalağa (heap) çevrilir.

Nümunə

Aşağıda ilkin massiv və nəticə olaraq qalaq olan son massiv göstərilib.

Alqoritmin realizasiyası

Gələcəkdə qalağa çevriləcək massivi elan edək.

#define MAX 1001
int a[MAX];

left funksiyası sol oğulun indeksini qaytarır.

int left(int i)
{
  return 2 * i;
}

right funksiyası sağ oğulun indeksini qaytarır.

int right(int i)
{
  return 2 * i + 1;
}

swap funksiyası $i$ və $j$ indeksli elementləri yerini dəyişir.

void swap(int &i, int &j)
{
  int temp = i;  i = j; j = temp;
}

heapify funksiyası $i$ indeksli təpədə kökü olan alt ağac üçün qalaq xassəsini bərpa edir. Üçüncü $n$ parametri saxlanılan qalağın ölçüsünü müəyyən edir.

void heapify(int a[], int i, int n)
{
  int largest = 0;
  int l = left(i);
  int r = right(i);

Cari $a [i]$ elementi və onun $a [l]$ və $a [r]$ oğulları arasında maksimal elementin indeksini tapırıq.

  if (l <= n && a[l] > a[i]) largest = l;
  else largest = i;
  if (r <= n && a[r] > a[largest]) largest = r;

Əgər $a [i]$ maksimal element deyilsə, onu maksimal oğulla yerini dəyişirik və sonra müvafiq alt ağacda (sol və ya sağ) qalaq xassəsini rekursiv şəkildə bərpa edirik.

  if (largest != i)
  {
    swap(a[i], a[largest]);
    heapify(a, largest, n);
  }
}

Proqramın əsas hissəsi. Giriş massivini $1$ indeksindən başlayaraq oxuyuruq.

scanf("%d", &n);
for (i = 1; i <= n; i++)
  scanf("%d", &a[i]);

$n /2$ -dən $1$ -ə qədər olan bütün indekslər üçün ardıcıl olaraq heapify prosedurunu icra edək.

for (i = n / 2; i > 0; i--)
  heapify(a, i, n);

max-qalaq olan nəticə massivini çap edirik.

for (i = 1; i <= n; i++)
  printf("%d ", a[i]);
printf("\n");

Java realizasiyası

import java.util.*;

public class Main 
{
  static int left(int i)
  {
    return 2 * i;
  }

  static int right(int i)
  {
    return 2 * i + 1;
  }

  static void swap(int a[], int i, int j)
  {
    int temp = a[i];  a[i] = a[j]; a[j] = temp;
  }
  
  //max - heap
  static void heapify(int a[], int i, int n) // n = qalağın ölçüsü
  {
    int largest = 0;
    int l = left(i);
    int r = right(i);

    if (l <= n && a[l] > a[i]) largest = l;
    else largest = i;
    if (r <= n && a[r] > a[largest]) largest = r;

    if (largest != i)
    {
      swap(a, i, largest);
      heapify(a, largest, n);
    }
  }
  
  public static void main(String[] args) {
    Scanner con = new Scanner(System.in);	  
    int n = con.nextInt();
    int m[] = new int[n+1];
    for(int i = 1; i <= n; i++)
      m[i] = con.nextInt();
    
    for(int i = n / 2; i > 0; i--)
      heapify(m,i,n);
    
    for(int i = 1; i <= n; i++)
      System.out.print(m[i] + " ");
    System.out.println();
    con.close();
  }
}

Java