package org.eda.actividad02.ejercicio01;

import java.util.ArrayList;
import java.util.Comparator;

import org.eda.estructurasdatos.Heap;

public class HeapSort<T> {

	public static <T> void sortHeap(ArrayList<T> scores1, Comparator<T> comp) {
		int cap = scores1.size();
		Heap<T> monticulo = new Heap<T>(cap, comp);
		for(int i = 0; i<cap; i++){
			monticulo.add(scores1.get(i));
		}
		for(int i = 0; i<cap; i++){
			scores1.set(i, monticulo.removeMin());
		}
	}

	public static <T> void heapSort(ArrayList<T> scores2, Comparator<T> comp) {
		makeHeap(scores2, comp);
	}

	public static <T> void makeHeap(ArrayList<T> lista, Comparator<T> comp){
		for (int i = lista.size() / 2; i >= 0; i--) {
			siftDown(lista, i, comp);
		}
		T elem;
		for (int i = lista.size(); (i > 1); i--) {

			swap(lista,0,i-1);
			siftDown(lista, 0,comp);
		}
		for (int i = 0; (i < lista.size() / 2); i++) {
			swap(lista, i, (lista.size()-i-1));
		}
	}

	protected static <T> void siftDown(ArrayList<T> lista, int primero,	Comparator<T> comp) {
		int parent = primero;
		int child = (parent << 1) + 1;
		while (child < lista.size()) {
			if (child < lista.size() - 1
					&& comp.compare(lista.get(child), lista.get(child + 1)) > 0)
				child++;
			if (comp.compare(lista.get(child), lista.get(parent)) >= 0) {
				break;
			}
			swap(lista, parent, child);
			parent = child;
			child = (parent << 1) + 1;
		}
	}

	private static <T> void swap(ArrayList<T> lista, int parent, int child) {
		T auxiliar = lista.get(parent);
		lista.set(parent, lista.get(child));
		lista.set(child, auxiliar);
	}

}