ShittyHEAP V2

package heap;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.NoSuchElementException;

public class ArrayHeapMinPQ<T> implements ExtrinsicMinPQ<T> {

    private ArrayList<PriorityNode> items;
    private HashMap<T, Integer> itemsMap;


    private class PriorityNode implements Comparable<PriorityNode> {
        private T item;
        private double priority;

        PriorityNode(T e, double p) {
            this.item = e;
            this.priority = p;
        }

        T getItem() {
            return item;
        }

        double getPriority() {
            return priority;
        }

        void setPriority(double priority) {
            this.priority = priority;
        }

        @Override
        public int compareTo(PriorityNode other) {
            if (other == null) {
                return -1;
            }
            return Double.compare(this.getPriority(), other.getPriority());
        }

        @Override
        @SuppressWarnings("unchecked")
        public boolean equals(Object o) {
            if (o == null || o.getClass() != this.getClass()) {
                return false;
            } else {
                return ((PriorityNode) o).getItem().equals(getItem());
            }
        }

        @Override
        public int hashCode() {
            return item.hashCode();
        }
    }


    public ArrayHeapMinPQ() {
        items = new ArrayList<>();
        itemsMap = new HashMap<T, Integer>();
    }

    private int downpath(int i) {
        int left = getLeft(i);
        if (left < items.size()) {
            double min = items.get(left).getPriority();
            boolean takeLeft = true;
            if (left + 1 < items.size()) {
                double right = items.get(left + 1).getPriority();
                if (Math.min(min, right) == right) {
                    min = right;
                    takeLeft = false;
                }
            }
            PriorityNode cur = items.get(i);
            if (cur.getPriority() <= min) {
                return -1;
            }
            int res = left + (takeLeft ? 0 : 1);
            PriorityNode resNode = items.get(res);
            itemsMap.put(cur.getItem(), res);
            itemsMap.put(resNode.getItem(), i);
            Collections.swap(items, res, i);
            return res;
        }
        return -1;
    }

    private int uppath(int i) {
        int parent = getParent(i);
        if (parent != -1) {
            PriorityNode curNode = items.get(i);
            PriorityNode parentNode = items.get(parent);
            if (curNode.getPriority() >= parentNode.getPriority()) {
                return -1;
            }
            itemsMap.put(curNode.getItem(), parent);

            itemsMap.put(parentNode.getItem(), i);
            Collections.swap(items, parent, i);
            return parent;
        }
        return -1;
    }

    /**
     * Repositions an out of place node in the right place in the heap
     */
    private void reposition(int i) {
        int res = downpath(i);
        boolean changed = false;
        while (res != -1) {
            i = res;
            res = downpath(i);
            changed = true;
        }
        if (!changed) {
            res = uppath(i);
            while (res != -1) {
                i = res;
                res = uppath(i);
            }
        }
    }

    private static int getParent(int i) {
        if (i == 0) {
            return -1;
        }
        return (i - 1) / 2;
    }

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


    /**
     * Adds an item with the given priority value.
     * Assumes that item is never null.
     * Runs in O(log N) time (except when resizing).
     *
     * @throws IllegalArgumentException if item is already present in the PQ
     */
    @Override
    public void add(T item, double priority) {
        if (contains(item)) {
            throw new IllegalArgumentException();
        }
        items.add(new PriorityNode(item, priority));
        itemsMap.put(item, items.size() - 1);
        reposition(items.size() - 1);
    }

    /**
     * Returns true if the PQ contains the given item; false otherwise.
     * Runs in O(log N) time.
     */
    @Override
    public boolean contains(T item) {
        return itemsMap.containsKey(item);
    }

    /**
     * Returns the item with the smallest priority.
     * Runs in O(log N) time.
     *
     * @throws NoSuchElementException if the PQ is empty
     */
    @Override
    public T getSmallest() {
        if (items.isEmpty()) {
            throw new NoSuchElementException();
        }
        return items.get(0).getItem();
    }

    /**
     * Removes and returns the item with the smallest priority.
     * Runs in O(log N) time (except when resizing).
     *
     * @throws NoSuchElementException if the PQ is empty
     */
    @Override
    public T removeSmallest() {
        PriorityNode res = items.get(0);
        itemsMap.remove(res.getItem());
        Collections.swap(items, 0, items.size() - 1);
        items.remove(items.size() - 1);
        reposition(0);
        return res.getItem();
    }

    /**
     * Changes the priority of the given item.
     * Runs in O(log N) time.
     *
     * @throws NoSuchElementException if the item is not present in the PQ
     */
    @Override
    public void changePriority(T item, double priority) {
        if (!contains(item)) {
            throw new NoSuchElementException();
        }
        int i = itemsMap.get(item);
        items.get(i).setPriority(priority);
        reposition(i);
    }

    /**
     * Returns the number of items in the PQ.
     * Runs in O(log N) time.
     */
    @Override
    public int size() {
        return items.size();
    }

    public void print() {
        for (PriorityNode node: items) {
            System.out.println(node.getPriority());
        }
    }
}