Max-heap#10166

Max-heap (Editorial)

Store the input data in an array $a$ . For all indices from $n /2$ down to $1$ , apply the heapify procedure in sequence. As a result, the array will be transformed into a max-heap.

Example

Below are the initial array and the final array that represents a heap.

Algorithm implementation

Declare an array that will later be transformed into a heap.

#define MAX 1001
int a[MAX];

The left function returns the index of the left son.

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

The right function returns the index of the right son.

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

The swap function exchanges the elements at indices $i$ and $j$ .

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

The heapify function restores the heap property for the subtree rooted at the node with index $i$ . The third parameter $n$ defines the size of the maintained heap.

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

Find the index of the largest element among the current element $a [i]$ and its children $a [l]$ and $a [r]$ .

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

If $a [i]$ is not the largest element, swap it with the largest son and then recursively restore the heap property in the corresponding subtree (left or right).

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

The main part of the program. Read the input array starting from index $1$ .

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

For all indices from $n /2$ down to $1$ , perform the heapify procedure in sequence.

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

Print the resulting array, which represents a max-heap.

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

Java implementation

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