#include <iostream>

void swap(int arr[], int a, int b) {
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}

void max_heap(int arr[], int size) {
	for (int i = 0; i < size; i++) {
		int leftChildIndex = 2 * i + 1,
			righChildtIndex = 2 * i + 2;

		if (righChildtIndex >= size || leftChildIndex >= size) {
			break;
		}

		if (leftChildIndex < size && arr[i] < arr[leftChildIndex]) {
			swap(arr, i, leftChildIndex);
		}

		if (righChildtIndex < size && arr[i] < arr[righChildtIndex]) {
			swap(arr, i, righChildtIndex);
		}
	}
}

void print(int arr[], int size) {
	for (int i = 0; i < size; i++) {
		std::cout << arr[i] << " ";
	}

	std::cout << std::endl;
}

void sort(int arr[], int size) {
	int orginalSize = size;
	while (size - 1 >= 1) {
		max_heap(arr, size);
		print(arr, size);
		swap(arr, 0, size-- - 1);
	}

	print(arr, orginalSize);
	std::cout << std::endl;
}

int main()
{
	int arr2[] = { 2, 1 };
	sort(arr2, 2);

	int arr[] = { 5, 1, 8, 3, 7 };
	sort(arr, 5);
}