10166. Max-куча

Задан массив целых чисел. Переставьте его элементы так, чтобы получилась max-куча.

Вход. В первой строке задано количество элементов массива n (n ≤ 1000).

Во второй строке содержится n целых чисел, каждое по модулю не превышает 10⁶.

Выход. Выведите переставленный массив, представляющий собой max-кучу. Если существует несколько решений, выведите любое.

Пример входа	Пример выхода
6 5 3 2 7 1 10	10 7 5 3 1 2

РЕШЕНИЕ

куча

Анализ алгоритма

Сохраним входные данные в массив а. Для всех индексов массива от 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();

}

}