/*
Autor: Marek Adamek
Temat: biblioteka stl: algorytm make_heap
*/


#include <vector>
#include <algorithm>
#include <iostream>

/*
Wiadomosc wstepne:
Kopiec - struktura danych oparta na drzewie binarnym w ktorym wartosci potomkow
wezla sa w tej samej relacji z wartoscia rodzica ((na przykład wartość rodzica 
jest zawsze większa lub równa wartości potomka)

Reprezentacja drzewa binarnego w postaci tablicy (zalozenie: indeksowanie od 0) 
- jesli rodzic ma index n to jego dzieci maja indeksy 2n+1 i 2n+2 

Aby skorzystac z alborytmu make_heap nalezy dolaczyc plik naglowkowy <algorithm>
Pliki <vector> i <iostream> zostaly dolaczone w celu wizuacji dzialania algorytmu
i nie sa wymagane do dzialania algorytnu

Zadaniem algorytmu make_heap() jest z utworzenie kopca z elementow wskazanych
przez parametry wywolania. Deklaracje funkcji make_heap() wygladaja nastepujaco:

template <class RandomAccessIterator>
  void make_heap ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void make_heap ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

Pierwsze dwa argumenty okreslaja zakres na jakim ma dzialac algorytm. Jest to zakres od
elementu wskazywanego przez first wlacznie do elementu wskazywanego przez last wylacznie.
Argumentem comp jest funcja w postaci: 
	bool comp(type a, type b), gdzie type jest typem obiektow wskazywanych przez first i last 
i bada relacje a<b. Jesli nie podamy zadnej funcji porownujacej jako argumentu, kompilator skorzysta 
z operatora < dla danego typu.

Jesli chcemy zbudowac kopiec w ktorym bedzie odwrocona relacja, tzn. element najmniejszy bedzie na gorze,
wystarczy jako funkcje porownujaca podac funcje ktora zwraca false gdy a<b i true gdy a>=b.
Przyklad takiego uzycia zostal zamieszcziny ponizej.
*/
using namespace std;

/*funcja pomocnicza drukujaca zawartosc vectora elementow typu int na standardowe wyjscie*/
void print(vector<int> v){
	for (vector<int>::const_iterator it = v.begin(); it != v.end(); ++it){
		cout<<*it<<" ";
	}
	cout<<endl;
}

/*funkcja odwacajaca relacje a<b, zostanie uzyta w celu stworzenia kopca w ktorym
na gorze znajduje sie element najmniejszy*/
bool mycompare(int a, int b){
	return !(a<b);
}

int main(){
	/*definicja vectora z liczbami, na ktorym bedziemy badali
	dzialanie algorytmu make_heap(). Podkreslam ze uzycie szablonu vector
	nie jest tutaj konieczne. Mozemy skorzystac z dowolnego kontenera dla ktorego 
	istnieje RandomAccessIterator np, std::list, czy nawet zwykla tablica*/
	int ints[] ={30, 4, 12, 6, 13, 75, 2, 32, 47, 26};
	vector<int> v(ints, ints + sizeof(ints)/sizeof(int));
	
	//wydrukowanie na standardowe wyjcie postaci poczatkowej naszej kolecji liczb
	cout<<"Przed: ";
	print(v);

	/*zbudowanie kopca. Iteratory begin() i end() definiuja zakres ktorym jest cala zawartosc
	vectora v. Brak wskazania funcji porownujacej sprawia ze zostanie uzyty openator < dla elementow 
	typu int*/
	make_heap(v.begin(), v.end());
	cout<<"Po: ";
	print(v);
	/*Funcji make_heap() mozemy uzywac takze do wyszukiwania 
	kolecji elementow elementu minimalnego lub maksymalnego,
	Znajduje sie on na pierwszym miejscu*/
	cout<<"Element najwiekszy: "<<v.front()<<endl;

	/*dzialania analogiczne do powyzszych, z tym ze zostala wskazana funkcja porownujaca.
	Odwraca ona relacje <, wiec zostanie utworzony kopiec w ktorym element najmniejszy jest na gorze*/
	make_heap(v.begin(), v.end(), mycompare);
	cout<<"Po z funcja porownujaca: ";
	print(v);
	cout<<"Element najmniejszy: "<<v.front()<<endl;

	/*Kolejnym zastosowaniem algorytmu make_head() jest sortowanie przez kopcowanie.
	Wywolanie make_heap() gwarantuje ze element ekstremalny znajduje 
	sie na pierwszym miejscu. Zatem mozemy przeniesc go na koniec zastosowac 
	algorytm dla reszty elementow. Powtarzajac to dzialanie do momentu gdy nie bedzie elementow
	z ktorych mozna zbudowac kopiec, otrzymamy posortowana kolecje elementow.
	*/
	int i = v.size(), tmp; 
	while (i > 0){
		make_heap(&v[0], &v[i]);
		--i;
		tmp = v[i];
		v[i] = v[0];
		v[0] = tmp;
	}
	cout<<"Sortowanie z uzyciem make_heap(): ";
	print(v);

	/*Aby posortowac elementy w druga strone wystarczy wskazac odpowiednia funkcje porownujaca*/
	i = v.size();
	while (i > 0){
		make_heap(&v[0], &v[i], mycompare);
		--i;
		tmp = v[i];
		v[i] = v[0];
		v[0] = tmp;
	}
	cout<<"Sortowanie z uzyciem make_heap() i funcji: ";
	print(v);

	return 0;
}

/* Po skompilowaniu i uruchomieniu tego programu na wyjsciu otrzymamy

Przed: 30 4 12 6 13 75 2 32 47 26 
Po: 75 47 30 32 26 12 2 4 6 13 
Element najwiekszy: 75
Po z funcja porownujaca: 2 4 12 6 13 75 30 32 47 26 
Element najmniejszy: 2
Sortowanie z uzyciem make_heap(): 2 4 6 12 13 26 30 32 47 75 
Sortowanie z uzyciem make_heap() i funcji: 75 47 32 30 26 13 12 6 4 2 
*/