Max-heap#10166

Max-heap (Editoriale)

Salviamo i dati in input nell'array $a$ . Per tutti gli indici dell'array da $n /2$ a $1$ applichiamo in sequenza la procedura heapify. Come risultato, l'array viene trasformato in uno max-heap.

Esempio

Di seguito sono riportati l'array originale e l'array finale, che rappresenta uno heap.

Implementazione dell'algoritmo

Dichiariamo un array, che in seguito sarà trasformato in uno heap.

#define MAX 1001
int a[MAX];

La funzione left restituisce l'indice del figlio sinistro.

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

La funzione right restituisce l'indice del figlio destro.

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

La funzione swap scambia tra loro gli elementi con indici $i$ e $j$ .

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

La funzione heapify ripristina la proprietà di heap per il sottoalbero con radice nel nodo di indice $i$ . Il terzo parametro $n$ definisce la dimensione dello heap mantenuto.

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

Troviamo l'indice dell'elemento massimo tra l'elemento corrente $a [i]$ e i suoi figli $a [l]$ e $a [r]$ .

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

Se $a [i]$ non è l'elemento massimo, lo scambiamo con il figlio massimo e successivamente ripristiniamo ricorsivamente la proprietà di heap nel sottoalbero corrispondente (sinistro o destro).

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

Parte principale del programma. Leggiamo l'array di input, a partire dall'indice $1$ .

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

Per tutti gli indici da $n /2$ a $1$ eseguiamo in sequenza la procedura heapify.

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

Stampiamo l'array risultante, che rappresenta uno max-heap.

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

Implementazione in 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