INF2220 fasit ukeoppgaver uke 5
===============================


OPPGAVE 2:
----------

Vis at det maksimale elementet i en bin?rheap, 
(det som har lavest prioritet)

a. vil ligge i en av l?vnodene
   
   anta at elementet ikke ligger i en l?vnode
   da har vi et maksimalt element, dvs. et
   element som er st?rre en barna/barnet,
   liggende i heapen, og heapen er ikke en
   heap, siden ordningskravet er brutt.


b. kan ligge i vilk?rlig l?vnode
   (her holder det ? vise at 
    bin?rheap-egenskapene holder
    for alle tilfeller)

   ta et element som er st?rre enn alle
   elementene i heapen, dette elementet
   kan erstatte alle l?vnoder, uten ? ?delegge
   heapkravene, dvs. strukturkravet eller
   ordningskravet. det er kun rekkef?lgen
   elementene blir lagt inn i heapen som
   avgj?r hvilken bladnode de blir liggende
   i, og det maksimale elementet m? en leite
   etter skal en finne det.

c. vis at en bin?rheap med et partall elementer
   vil ha n?yaktig N/2 l?vnoder.

   tenk p? at elementene ligger i en fullpakket
   array, vi p?st?r at de N/2 siste elementene
   vil v?re bladnoder. kanskje enklest ? se 
   ved et eksempel f?rst, se p? heapen
   der vi har 10 elementer liggende i en array:

    0 1 2 3 4 5 6 7 8 9 10.......
   |-|x|x|x|x|x|x|x|x|x|x| | | | |

   vi har ingenting liggende i array posisjon 0
   men fra 1 til 10 har vi elementer. p?standen
   er n? at element 6,7,8,9,10 er bladnoder.
   hvis n? 6 skulle hatt barn, og ikke v?rt
   bladnode, hvor hadde det barnet da blitt liggende?

   venstre barn = 6*2   = 12
   h?yre   barn = 6*2+1 = 13

   dette er utenfor rekkevidde pga. at heapen
   bare inneholder 10 elementer. samme argument for 7 osv.

   generelt s? har vi at (N/2 + 1) * 2 > N/2
   s? vi vil uansett g? utenfor heapen for
   de siste N/2 indeksene.






OPPGAVE 3:
----------

================code=====================

    int[] sort(int[] a){

        clearHeap();

        int[] result = new int[a.length];

        for(int i = 0; i < a.length; i++){
            insert(a[i]);
        }

        int cnt = 0;
        while(hasMoreElements()){
            result[cnt++] = deleteMin();
        }

        return result;
        
    }