B5

package sk.upjs.paz.cvicenie05;

import java.util.Arrays;

public class PrioritnyRad {

    private int[] arr;
    private int count;

    public PrioritnyRad(int kapacita) {
        arr = new int[kapacita];
        count = 0;
    }

    public boolean offer(int cislo) {
        arr[count] = cislo;
        count++;
        // narusitel je v liste, ak by to bolo maximum tak sa musi dostat do korena, resp. na svoje miesto
        uhaldujZdola();
        // true ak bol uspesne pridany
        return true;
    }

    private void uhaldujZdola() {
        int idx = count - 1;
        while (idx > 0) {
            int parentIdx = (idx - 1) / 2;
            System.out.println("   porovnavam " + parentIdx + " a " + idx);
            if (arr[parentIdx] < arr[idx]) {
                vymen(parentIdx, idx);
            }
            idx = parentIdx;
        }
    }

    public int poll() {
        //if (isEmpty()) return Integer.MIN_VALUE;
        int res = arr[0];
        // narusitel je v koreni, uhalduje sa
        uhaldujZhora();
        count--;
        return res;
    }

    private void uhaldujZhora() {
        int narusitelIdx = 0;
        int poslednyIdx = count - 1;
        // kod haldovania kopirovany z prednasky
        while (true) {
            int najvacsiIdx = narusitelIdx;
            int lavySynIdx = narusitelIdx * 2 + 1;
            int pravySynIdx = narusitelIdx * 2 + 2;
            if ((lavySynIdx <= poslednyIdx) &&
                    (arr[lavySynIdx] > arr[najvacsiIdx]))
                najvacsiIdx = lavySynIdx;
            if ((pravySynIdx <= poslednyIdx) &&
                    (arr[pravySynIdx] > arr[najvacsiIdx]))
                najvacsiIdx = pravySynIdx;
            if (najvacsiIdx == narusitelIdx)
                break;
            vymen(narusitelIdx, najvacsiIdx);
            narusitelIdx = najvacsiIdx;
        }
    }

    public boolean isEmpty() {
        return count == 0;
    }


    private void vymen(int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    @Override
    public String toString() {
        return "PrioritnyRad{" +
                "arr=" + Arrays.toString(arr) +
                ", count=" + count +
                '}';
    }

    public static void main(String[] args) {
        PrioritnyRad p = new PrioritnyRad(10);
        int[] a = {5, 3, 1, 8, 17};
        for (int i = 0; i < a.length; i++) {
            p.offer(a[i]);
            System.out.println(p);
        }
        System.out.println("-------");
        for (int i = 0; i < 5; i++) {
            p.poll();
            System.out.println(p);
        }
        System.out.println("-------");
        for (int i = 0; i < a.length; i++) {
            p.offer(a[i]);
            System.out.println(p);
        }




    }
}