Max-купа#10166

Max-купа (Розбір)

Збережемо вхідні дані в масив $a$ . Для всіх індексів масиву від $n /2$ до $1$ послідовно застосуємо процедуру heapify. У результаті масив перетвориться на max-купу.

Приклад

Нижче наведено вихідний масив та кінцевий масив, який є купою.

Реалізація алгоритму

Оголосимо масив, який надалі буде перетворено на купу.

#define MAX 1001
int a[MAX];

Функція left повертає індекс лівого сина.

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

Функція right повертає індекс правого сина.

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

Функція swap міняє місцями елементи з індексами $i$ та $j$ .

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

Функція heapify відновлює властивість купи для піддерева з коренем у вершині з індексом $i$ . Третій параметр $n$ задає розмір купи, що підтримується.

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

Знаходимо індекс максимального елемента серед поточного елемента $a [i]$ та його синів $a [l]$ і $a [r]$ .

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

Якщо $a [i]$ не є максимальним елементом, міняємо його місцями з максимальним сином і далі рекурсивно відновлюємо властивість купи у відповідному піддереві (лівому або правому).

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

Основна частина програми. Читаємо вхідний масив, починаючи з індексу $1$ .

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

Для всіх індексів від $n /2$ до $1$ послідовно виконаємо процедуру heapify.

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

Виводимо результуючий масив, який являє собою max-купу.

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

Java реалізація

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 = size of a heap
  {
    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