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



OPPGAVE 1:
----------

Tegn opp en bin?rheap etter at vi har satt
inn disse prioritetene: 10, 2, 1, 14, 6, 5, 7


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

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

a. vil ligge i en av l?vnodene

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

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

   denne oppgaven er kanskje litt vanskelig
   men b?r v?re overkommelig hvis en tenker
   p? representasjonen til en bin?rheap.





Ta utgangspunkt i kodebiten under som implementerer
en bin?rheap for positive heltall. Dvs. en bin?rheap
der en setter inn prioritet, ikke tilknyttet noe objekt.

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

implementer funksjonen sort, som utf?rer en
heap-sort ved ? bruke denne bin?rheapen.

HINT: se main funksjonen...



OPPGAVE 4: [ekstra]
---------

lag en ny implementasjon, eller modifiser Heap
implementasjonen under til ? virke for elementer
som implementerer Heapable interfacet:

interface Heapable{
    // returns a positive number
    public int priority();
}

dvs. 

void insert(Heapable element) 
Heapable deleteMin() 

osv. m? lages

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


/**
 * small example of a heap implementation.
 * it does not sort arbitrary elements into
 * a heap, but only the priorities, i.e.,
 * when we insert we insert a priority, and
 * no object connected to this priority. 
 * this will hopefully simplify things a bit
 * and still be enough to illustrate the idea.
 *
 * priorities are positive numbers in this
 * example, so 1,2,3,4,5... are  priorities, 
 * if you start to make these smaller things 
 * will get wierd fast.
 *
 * @author bjarneh@ifi.uio.no
 */

class Heap{

    int[] bintree;
    int freepos;


    Heap(){
        this(65);
    }

    Heap(int capacity){

        if(capacity < 10) {
            capacity = 10;
        }

        clearHeap(capacity);
    }

    void clearHeap(int capacity){

        bintree = new int[capacity];

        for(int i = 0; i < capacity; i++){
            bintree[i] = 0;
        }

        // assume positive values
        bintree[0] = -1;
        freepos = 1;
    }

    void clearHeap(){
        if(bintree != null){
            clearHeap(bintree.length);
        }else{
            clearHeap(65);
        }
    }


    int[] sort(int[] a){

        //TODO

        return null;
    }

    int parent(int elmt){
        return (int) elmt/2;
    }

    int left(int elmt){
        return 2*elmt;
    }

    int right(int elmt){
        return (2*elmt) + 1;
    }

    int size(){
        return bintree.length;
    }

    void resize(){

        int[] big_bintree = new int[bintree.length * 2];

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

        bintree = big_bintree;
    }

    void insert(int priority){

        if(freepos >= size()){
            resize();           
        }

        // insert at next free position
        bintree[freepos] = priority;

        // push it up into the right position
        percolateUp(freepos);

        // make room for next element
        freepos++;

    }

    int deleteMin(){

        int top;
        if(freepos > 1){

            // store the element we remove from the heap
            top = bintree[1]; 

            // move last element of heap to the top
            bintree[1] = bintree[ --freepos ];

            // delete last element after its moved to top
            bintree[freepos] = 0;

            // make it float down to right position
            percolateDown(1);

            // return element from top of heap
            return top;
        
        }else{
        
            return -1;
        
        }
    }


    void percolateDown(int pos){

        if(largeLeftChild(pos) || largeRightChild(pos)){

            int minchild = findMinChild(pos);

            swap(pos, minchild);

            percolateDown(minchild);
        }
    }

    // direction becomes 'left' or 'rigth' value
    // depending on which of the two nodes who has
    // the smallest value. we want to swap the parent 
    // with the smallest child, when we percolateDown

    int findMinChild(int pos){

        // just to avoid: 
        // variable may not have been initialized 
        int min = Integer.MAX_VALUE;
        int direction = Integer.MAX_VALUE;
        
        if(largeLeftChild(pos)){
            min = bintree[left(pos)];
            direction = left(pos);
        }

        if(largeRightChild(pos)){

            int tmp = bintree[right(pos)];
            
            if(tmp < min){
                direction = right(pos);
            }
        }
        
        return direction;
    }

    boolean largeLeftChild(int pos){
        return (left(pos) < bintree.length && 
                bintree[left(pos)] > 0 && 
                bintree[pos] > bintree[left(pos)]);
    }

    boolean largeRightChild(int pos){
        return (right(pos) < bintree.length && 
                bintree[right(pos)] > 0 && 
                bintree[pos] > bintree[right(pos)]);
    }

    void swap(int p1, int p2){

        int tmp = bintree[ p2 ];
        bintree[ p2 ] = bintree[ p1 ];
        bintree[ p1 ] = tmp;
    }

    void percolateUp(int pos){

        if(bintree[pos] < bintree[ parent(pos) ]){
            swap(pos, parent(pos));
            percolateUp(parent(pos));
        }
    }

    boolean hasMoreElements(){
        return freepos > 1;
    }


    // below this line we have debugging and testing

    public static void main(String[] args){

        int[] elms = {2,33,23,232,11,3,7,22,17,5,53,32};

        Heap heap = new Heap( elms.length + 2 );

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

        heap.printarray();
        heap.treeprint();

        while(heap.hasMoreElements()){
            System.out.print(" "+heap.deleteMin());
        }
        System.out.println("");

    }


    // with no input parameter, printarray just
    // writes content of bintree array to stdout
    void printarray(){
        printarray(bintree);
    }

    // writes content of int array to standard out
    void printarray(int[] a){
        System.out.print("\n[");
        for(int i = 0; i < a.length -1; i++){
            System.out.print(a[i]+", ");
        }
        System.out.println(a[ a.length -1 ]+"]");
    }


    // to get some idea of how deep our tree is
    void treeprint(){
        treeprint(1, " ");
    }


    // to get some idea of how deep our tree is
    void treeprint(int a, String offset){

        System.out.println(offset+""+bintree[a]);

        if(left(a) < bintree.length && bintree[left(a)] != 0){
            treeprint(left(a), offset+"- ");
        }
        if(right(a) < bintree.length && bintree[right(a)] != 0){
            treeprint(right(a), offset+"- ");
        }
    }
}