Heap Sort (Java)

gistfile1.txt

interface DSAComparable<E> {
    /** Vrati true, pokud je this (ostre) mensi nez other, false jinak. */
    boolean less(E other);
    /** Vrati nejmensi prvek ze vsech prvku typu E (tzn. prvek, ktery je mensi nez
     * jakykoli jiny prvek typu E). Vracena hodnota nezavisi na this, jen na E.
     */
    E getLeastElement();
    /** Vrati nejvetsi prvek ze vsech prvku typu E (tzn. prvek, ktery je vetsi
     * nez jakykoli jiny prvek typu E). Vracena hodnota nezavisi na this, jen na E.
     */
    E getGreatestElement();
}
 
/** Rozhrani HeapStorage reprezentuje pole, do ktereho si halda uklada svoje prvky. */
interface HeapStorage<E extends DSAComparable<E>> {
 
    /** Vrati aktualni velikost HeapStorage. */
    int getSize();
 
    /** Vrati true, pokud je aktualni velikost HeapStorage nulova. */
    boolean isEmpty();
 
    /** Vrati prvek na indexu index (1 <= index <= getSize()). Pokud je index
     * mensi nebo roven nule, vrati nejvetsi prvek. Pokud je index vetsi nez
     * velikost pole, vrati nejmensi prvek. V obou pripadech muzete predpokladat,
     * ze v HeapStorage je alespon jeden prvek.
     */
    E getElement(int index);
 
    /** Prohodi prvky na indexech index a index2 (1 <= index, index2 <= getSize()). */
    void swap(int index, int index2);
 
    /** Odstrani posledni prvek (tzn. snizi velikost teto HeapStorage) a vrati jeho hodnotu. */
    E extractLast();
 
    /** Vlozi prvek a vrati jeho index. Muzete predpokladat, ze ve spodnim poli je dost mista. */
    int insertLast(E element);
}




class Homework3<E extends DSAComparable<E>> implements HeapStorage<E>{ 
    E[]elements;
    int numberOfElements;

    Homework3(E[] elements) {
        this.elements = elements;
        for (int i = 0; i < elements.length; i++) {
            if(elements[i]!=null){
                numberOfElements++;
            }
        }
    }

    public int getSize() {
        return numberOfElements;
    }

    public boolean isEmpty() {
        if(this.elements.length<1){
            return true;
        }
        return false;
    }

    public E getElement(int index) {
        if(index<=0){
            E smallest=elements[0];
            int indexOfSmallest=0;
            for (int i = 0; i < numberOfElements; i++) {
                if(elements[i].less(smallest)){
                    smallest=elements[i];
                    indexOfSmallest=i;
                }
            }
            return elements[indexOfSmallest];
        }
        if(index>elements.length){
            E biggest=elements[0];
            int indexOfBiggest=0;
            for (int i = 0; i < numberOfElements; i++) {
                if(!(elements[i].less(biggest))){
                    biggest=elements[i];
                    indexOfBiggest=i;
                }
            }
            return elements[indexOfBiggest];
        }
        return elements[--index];
    }

    public void swap(int index, int index2) {
        if(index<1 || index2<1){
            return;
        }
        --index;--index2;
        E tmp = elements[index2];
        elements[index2] = elements[index];
        elements[index] = tmp;
    }


    public E extractLast() {
        if (!containsAtLeastOneElement()){
            return null;
        }
        int indexOfLast=numberOfElements-1;
        E last = elements[indexOfLast];
        elements[indexOfLast]=null;
        numberOfElements--;
        return last;
    }

    public int insertLast(E element) {
        elements[numberOfElements]=element;
        numberOfElements++;
        return numberOfElements;
    }

    public void printElements(){
        for (int i = 0; i < elements.length; i++) {
            if(elements[i]!=null){
                System.out.println(((MyNum) elements[i]).value);
            }
            else{
                System.out.println("NULL");
            }
        }
        System.out.println("==============");
    }
    public boolean containsAtLeastOneElement(){
        for (int i = 0; i < elements.length; i++) {
            if(elements[i]!=null){
                return true;
            }
        }
        return false;
    }
}



class Heap<E extends DSAComparable<E>> {
    HeapStorage<E> storage;
    int numberOfElements;

    Heap(HeapStorage<E> storage) {
        this.storage=storage;
        numberOfElements=this.getNumberOfElements();
        for (int i=numberOfElements/2; i>0; i--){
            heapify(i);
        }
    }

     void heapify(int index) {
        int left = (2 * index);
        int right =((2 * index) + 1);
        if(storage.getElement(left)==null){
            return;
        }

        int largest = (index);
        if (left <= numberOfElements && storage.getElement(index).less(storage.getElement(left))) {
            largest = left;
            }
        else{
            largest=index;
        }
        if (right <= numberOfElements && storage.getElement(largest).less(storage.getElement(right))) {
            largest = right;
            }
        if((storage.getElement(largest).less(storage.getElement(index))) || storage.getElement(index).less(storage.getElement(largest))){
            storage.swap(index,largest);
            heapify(largest);
        }

    }

    void insert(E element) {
        int indexOfLast=storage.insertLast(element);
        numberOfElements++;
        bubbleUp(element, indexOfLast);
        heapify(1);
    }
    
    void bubbleUp(E element,int index){
        int parentIndex=index/2;
        for (int i = parentIndex; i > 0; i=i/2) {
            heapify(i);
        }
    }
    

    E extractMax() {
        heapify(1);
        E max = storage.getElement(1);
        storage.swap(1, numberOfElements);
        storage.extractLast();
        numberOfElements--;
        heapify(1);
        return max;
    }

    boolean isEmpty() {
        if(storage.getSize()<1){
            return true;
        }
        return false;
    }
 
    static <E extends DSAComparable<E>> void heapsort(E[] array) {//static <E> void heapsort(E[] array) {
        HeapStorage hs = new Homework3(array);
        Heap heap = new Heap(hs);
        heap.heapify(1);
        for (int i = heap.numberOfElements; i >= 2; i--) {
            hs.swap(1, i);
            heap.numberOfElements--;
            heap.heapify(1);
        }
    }
    
    public static void main(String[] args) {

	DSAComparable[] x = new MyNum[] {
		new MyNum(10),
		new MyNum(2),
		new MyNum(8),
		new MyNum(3),
		new MyNum(1),
		new MyNum(4),
                new MyNum(6),
                //new MyNum(7),
                null,
                null,
                null,
                null,
                null,
                null,
                null,
                null,
                null,
	};
        
	//heapsort(x);
        Homework3 hw = new Homework3(x);
        Heap h = new Heap(hw);
        //System.out.println(((MyNum) h.storage.getElement(5534)).value+" MAX PRVEK INDEX");
        h.printStorage();
        h.insert(new MyNum(5));
        h.extractMax();
        h.insert(new MyNum(50));

        
        
        h.printStorage();
        
        //h.extractMax();
        //System.out.println(((MyNum) h.storage.getElement(5534)).value+" MAX PRVEK INDEX");
        //h.printStorage();
        //h.extractMax();

        //hw.printElements();

        //hw.printElements();
        //hw.insertLast(new MyNum(3));
        //heapsort(x);
        //hw.printElements();
        //hw.printElements();
        //Heap h = new Heap(hw);
        //h.printStorage();
        
        //System.out.println(((MyNum) x[x.length]).value);
        //DSAComparable e = hw.extractLast();
        
        //System.out.println(((MyNum) e));
}


    void printStorage(){
        for (int i = 1; i <= storage.getSize(); i++) {
            System.out.println(((MyNum) storage.getElement(i)).value);
        }
        System.out.println("============");
    }

    int getNumberOfElements(){
        int citac=0;
        for (int i = 1; i <= storage.getSize(); i++) {
            if(storage.getElement(i)!=null){
                citac++;
            }
        }
        return citac;
    }
}