/*
Masive de date  - Vectori
Aplicatii ale vectorilor :

1) Algorimul de sortare SELECT SORT
2) Algorimul de sortare BUBBLE SORT
3) Algorimul de sortare INSERT SORT
-------------------------------------------
4) Algorimul de sortare HEAP SORT

( sortare cu gramezi )

Def(1)
Prin heap(gramada) intelegem o structura de date interiorul careia
sunt verificate proprietatile

(a) Element  pe pozitia i daca are relationari ( descendente ) acestea sunt
      pe pozitiile 2*i si 2*i+1
(b) Element  pe pozitia i daca are relationari ( descendente ) detine o
      informatie >= decat a descendentilor sai


Un heap poate fi imaginat ca un arbore binar in interiorul caruia
fiecare nod are un nume si o informatie
Descendentele daca exista sunt ramuri in acest arbore

exemplu :

                   *1 [ 300 ]               nod i=1 radacina  are doi fii
                /           \
             *2 [32]     *3 [45]
            /             \
           *4 [ 22 ]   *5 [7]

OBS :
Intr-un heap informatia de valoare maxima se afla in radacina

Idee heasort :
{1}
                *1 [ 300 ]
           ----------------------
                /          \
             *2 [32]     *3 [45]
            /             \
           *4 [ 22 ]   *5 [7]

{2}

 reorganizarea :
           ----------------------
                /          \
             *2 [32]     *3 [45]
            /             \
           *4 [ 22 ]   *5 [7]

ca heap !

=================================
Construierea unui heap !!!!!

heapul va  fi reprezentat sub forma de vector

       ---------------------------------
V :  |  300  |  32 |  45  |   22 |  7 |
        ---------------------------------
          1           2        3        4       5

in care index inseamna nume de nod si continut inseamna
informatie atasata !!!!

Cum ???

pas 1 : consider heapul singleton  ( format dintr-un singur element )

pas 2 : in heap adaug nodul i
            daca stiu cum se numeste nodul deduc numele tatalui
            verific buna relatie tata fiu

exemplu :
                  32 , 7 ,300 , 45 , 22

        pas (1)
             *1[32]

        pas   2
                *1[32]
                /
            *2[7]


        pas   3

                *1[32]
                /      \                         verific buna relatie tata fiu  : NU !!!!
            *2[7]     3[300]               interschimb V[tata] cu V[fiu]


                 *1[300]                    operatie urmata de un sir de verificari
                /      \                        pe verticala ( cu scopul de a decide
                                                  daca nu am stricat heapul anterior
            *2[7]     3[32]
                                                   sirul verificarilor pe verticala
                                                   se opreste fie cand ies din gramada
                                                   fie cand gaseses advertenta

     pas   4

                *1[300]
                /      \

            *2[7]     3[32]
         /
        *4 [45]


                *1[300]
                /      \

            *2[45]     3[32]
         /
        *4 [7]


    pas 5

                *1[300]
                /      \

            *2[45]     3[32]
         /          \
        *4 [7]     *5[22]


        Avem heap
        V : 300,45,32,7,22

        OBS
        Organizarea unui set ca heap NU ESTE UNICA !!!

*/
#include<iostream>
using namespace std;
int n,V[100];
int main()
{int fiu;
int tata;
cout<<"n=";cin>>n;
for(int i=1;i<=n;i=i+1) { cout<<endl<<"V["<<i<<"]=";cin>>V[i];}
// for( int k .....
       //  {
    for(int i=k;i<=n-1;i=i+1)   // sirul de insertiilor de efectuat
            {    fiu=i+1; tata=fiu/2;
                    while ( ( V[tata]  < V[fiu] ) && (tata>=1) ){
                                                                   swap(V[tata],V[fiu]);
                                                                    fiu=tata;
                                                                    tata=fiu/2;
                                                                    } }
        // }
cout<<endl; for(int i=1;i<=n;i=i+1) { cout<<V[i]<<" "; } }