#include <stdio.h>
#include <stdlib.h>

#include "Item.h"

#define MAX_ITEMS 100000000

static void heapSort(Item items[], int size);
static void heapify(Item items[], int size);
static void deheapify(Item items[], int size);
static void fixDown(Item items[], int i, int N);
static void swap(Item items[], int i, int j);
static void display(Item items[], int size);

int main(void)
{
	Item *items = malloc(MAX_ITEMS * sizeof(Item));
	if (items == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	// read input
	int n = 0;
	while (n < MAX_ITEMS && read(items[n]) == 1) {
		n++;
	}

	heapSort(items, n);

	// display(items, n;
	(void) display;

	free(items);
}

static void heapSort(Item items[], int size)
{
	heapify(items, size);
	deheapify(items, size);
}

static void heapify(Item items[], int size) 
{
	for (int i = size / 2; i >= 0; i--) {
		fixDown(items, i, size - 1);
	}
}

static void deheapify(Item items[], int size)
{
	while (size > 1) {
		swap(items, 0, size - 1);
		size--;
		fixDown(items, 0, size - 1);
	}
}

static void fixDown(Item items[], int i, int N)
{
	while (2 * i + 1 <= N) {
		int j = 2 * i + 1;
		if (j < N && lt(items[j], items[j + 1])) j++;
		if (ge(items[i], items[j])) break;
		swap(items, i, j);
		i = j;
	}
}

static void swap(Item items[], int i, int j)
{
	Item temp = items[i];
	items[i] = items[j];
	items[j] = temp;
}

static void display(Item items[], int size)
{
	for (int i = 0; i < size; i++) {
		show(items[i]);
		printf("\n");
	}
}