Приоритетна редица - Java Задача 2 (1 / 1)
Дадена ви е max heap - структура што ги има дефинирано методите за додавање на нов елемент и
за отстранување на максималниот елемент.
Разгледајте го почетниот код за heap структурата и дополнете ја функцијата adjustUp
која што ги менува позициите на елементот што се наоѓа на позиција i во heap дрвото (со моментална големина n) и
на неговиот родител се додека постои нарушување на heap својството.
Во првата линија ќе ви биде даден бројот на команди C,
а во наредните C линии ќе ви бидат дадени командите што можат да го имаат следниот облик:

INSERT [број] - со која потребно е да го додадете новиот број во heap - дрвото
REMOVE MAX - со која е потребно да го извадите максималниот елемент од heap - дрвото и да го испечатите на излез
PRINT HEAP - со која е потребно да се испечати содржината на низата со елементи во heap - дрвото

Име на класата: PriorityQueueTest

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.StringTokenizer;

class Heap<E extends Comparable<E>> {

    private int N;
    private E elements[];

    private Comparator<? super E> comparator;

    private int compare (E k1, E k2) {
    return (comparator==null ? k1.compareTo(k2) : comparator.compare(k1, k2));
    }

    int getParent(int i) {
        return (i+1)/2-1;
    }

    public E getAt(int i) {
        return elements[i];
    }

    int getLeft(int i) {
        return (i+1)*2-1;
    }

    int getRight(int i) {
        return (i+1)*2;
    }

    void setElement(int index, E elem) {
        elements[index] = elem;
    }

    void swap(int i, int j) {
        E tmp = elements[i];
        elements[i] = elements[j];
        elements[j] = tmp;
    }

    void adjust(int i, int n){

        while (i < n) {

            int left = getLeft(i);
            int right = getRight(i);
            int largest = i;

            if ((left < n)&&(elements[left].compareTo(elements[largest]) > 0))
                largest = left;
            if ((right < n)&&(elements[right].compareTo(elements[largest]) > 0))
                largest = right;

            if (largest == i)
                break;

            swap(i, largest);
            i = largest;

        }

    }

    void buildHeap() {
        int i;
        for (i=elements.length/2-1;i>=0;i--)
            adjust(i, elements.length);
    }

    public void heapSort() {
        int i;
        buildHeap();
        for (i=elements.length;i>1;i--) {
            swap(0, i-1);
            adjust(0, i-1);
        }
    }

    @SuppressWarnings("unchecked")
    public Heap(int size) {
        elements = (E[])new Comparable[size];
        N = 0;
    }

    public boolean insert(E elem) {
        if (N == elements.length)
            return false;   // there is not enough space in the array
        elements[N] = elem;
        N++;
        adjustUp(N-1, N);
        return true;
    }

    public E removeMax() {
        if (N == 0)
            return null;
        E tmp = elements[0];
        elements[0] = elements[N-1];
        N--;
        adjust(0, N);
        return tmp;
    }

    void adjustUp(int i, int n){
        while(i!=0){
            if(this.getAt(i).compareTo(this.getAt(this.getParent(i)))>0)
                this.swap(i,this.getParent(i));
                i=this.getParent(i);
        }
    }

    public void printHeapArray() {
        int i;
        for (i=0;i<N;i++)
            System.out.print(elements[i].toString()+" ");
        System.out.println();
    }

}

public class PriorityQueueTest {

    public static void main(String[] args) throws Exception {
        int i;

        Heap<Integer> h = new Heap<Integer>(1000000);

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for (i=0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String comm = st.nextToken();
            if (comm.equals("INSERT")) {
                int num = Integer.parseInt(st.nextToken());
                h.insert(new Integer(num));
            } else if (comm.equals("REMOVE")) {
                System.out.println(h.removeMax());
            } else if (comm.equals("PRINT")) {
                h.printHeapArray();
            }
        }

        br.close();

    }

}