SHARE
TWEET

ShittyHEAP V2

a guest Oct 21st, 2019 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package heap;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Collections;
  5. import java.util.HashMap;
  6. import java.util.NoSuchElementException;
  7.  
  8. public class ArrayHeapMinPQ<T> implements ExtrinsicMinPQ<T> {
  9.  
  10.     private ArrayList<PriorityNode> items;
  11.     private HashMap<T, Integer> itemsMap;
  12.  
  13.  
  14.     private class PriorityNode implements Comparable<PriorityNode> {
  15.         private T item;
  16.         private double priority;
  17.  
  18.         PriorityNode(T e, double p) {
  19.             this.item = e;
  20.             this.priority = p;
  21.         }
  22.  
  23.         T getItem() {
  24.             return item;
  25.         }
  26.  
  27.         double getPriority() {
  28.             return priority;
  29.         }
  30.  
  31.         void setPriority(double priority) {
  32.             this.priority = priority;
  33.         }
  34.  
  35.         @Override
  36.         public int compareTo(PriorityNode other) {
  37.             if (other == null) {
  38.                 return -1;
  39.             }
  40.             return Double.compare(this.getPriority(), other.getPriority());
  41.         }
  42.  
  43.         @Override
  44.         @SuppressWarnings("unchecked")
  45.         public boolean equals(Object o) {
  46.             if (o == null || o.getClass() != this.getClass()) {
  47.                 return false;
  48.             } else {
  49.                 return ((PriorityNode) o).getItem().equals(getItem());
  50.             }
  51.         }
  52.  
  53.         @Override
  54.         public int hashCode() {
  55.             return item.hashCode();
  56.         }
  57.     }
  58.  
  59.  
  60.     public ArrayHeapMinPQ() {
  61.         items = new ArrayList<>();
  62.         itemsMap = new HashMap<T, Integer>();
  63.     }
  64.  
  65.     private int downpath(int i) {
  66.         int left = getLeft(i);
  67.         if (left < items.size()) {
  68.             double min = items.get(left).getPriority();
  69.             boolean takeLeft = true;
  70.             if (left + 1 < items.size()) {
  71.                 double right = items.get(left + 1).getPriority();
  72.                 if (Math.min(min, right) == right) {
  73.                     min = right;
  74.                     takeLeft = false;
  75.                 }
  76.             }
  77.             PriorityNode cur = items.get(i);
  78.             if (cur.getPriority() <= min) {
  79.                 return -1;
  80.             }
  81.             int res = left + (takeLeft ? 0 : 1);
  82.             PriorityNode resNode = items.get(res);
  83.             itemsMap.put(cur.getItem(), res);
  84.             itemsMap.put(resNode.getItem(), i);
  85.             Collections.swap(items, res, i);
  86.             return res;
  87.         }
  88.         return -1;
  89.     }
  90.  
  91.     private int uppath(int i) {
  92.         int parent = getParent(i);
  93.         if (parent != -1) {
  94.             PriorityNode curNode = items.get(i);
  95.             PriorityNode parentNode = items.get(parent);
  96.             if (curNode.getPriority() >= parentNode.getPriority()) {
  97.                 return -1;
  98.             }
  99.             itemsMap.put(curNode.getItem(), parent);
  100.  
  101.             itemsMap.put(parentNode.getItem(), i);
  102.             Collections.swap(items, parent, i);
  103.             return parent;
  104.         }
  105.         return -1;
  106.     }
  107.  
  108.     /**
  109.      * Repositions an out of place node in the right place in the heap
  110.      */
  111.     private void reposition(int i) {
  112.         int res = downpath(i);
  113.         boolean changed = false;
  114.         while (res != -1) {
  115.             i = res;
  116.             res = downpath(i);
  117.             changed = true;
  118.         }
  119.         if (!changed) {
  120.             res = uppath(i);
  121.             while (res != -1) {
  122.                 i = res;
  123.                 res = uppath(i);
  124.             }
  125.         }
  126.     }
  127.  
  128.     private static int getParent(int i) {
  129.         if (i == 0) {
  130.             return -1;
  131.         }
  132.         return (i - 1) / 2;
  133.     }
  134.  
  135.     private static int getLeft(int i) {
  136.         return i * 2 + 1;
  137.     }
  138.  
  139.  
  140.     /**
  141.      * Adds an item with the given priority value.
  142.      * Assumes that item is never null.
  143.      * Runs in O(log N) time (except when resizing).
  144.      *
  145.      * @throws IllegalArgumentException if item is already present in the PQ
  146.      */
  147.     @Override
  148.     public void add(T item, double priority) {
  149.         if (contains(item)) {
  150.             throw new IllegalArgumentException();
  151.         }
  152.         items.add(new PriorityNode(item, priority));
  153.         itemsMap.put(item, items.size() - 1);
  154.         reposition(items.size() - 1);
  155.     }
  156.  
  157.     /**
  158.      * Returns true if the PQ contains the given item; false otherwise.
  159.      * Runs in O(log N) time.
  160.      */
  161.     @Override
  162.     public boolean contains(T item) {
  163.         return itemsMap.containsKey(item);
  164.     }
  165.  
  166.     /**
  167.      * Returns the item with the smallest priority.
  168.      * Runs in O(log N) time.
  169.      *
  170.      * @throws NoSuchElementException if the PQ is empty
  171.      */
  172.     @Override
  173.     public T getSmallest() {
  174.         if (items.isEmpty()) {
  175.             throw new NoSuchElementException();
  176.         }
  177.         return items.get(0).getItem();
  178.     }
  179.  
  180.     /**
  181.      * Removes and returns the item with the smallest priority.
  182.      * Runs in O(log N) time (except when resizing).
  183.      *
  184.      * @throws NoSuchElementException if the PQ is empty
  185.      */
  186.     @Override
  187.     public T removeSmallest() {
  188.         PriorityNode res = items.get(0);
  189.         itemsMap.remove(res.getItem());
  190.         Collections.swap(items, 0, items.size() - 1);
  191.         items.remove(items.size() - 1);
  192.         reposition(0);
  193.         return res.getItem();
  194.     }
  195.  
  196.     /**
  197.      * Changes the priority of the given item.
  198.      * Runs in O(log N) time.
  199.      *
  200.      * @throws NoSuchElementException if the item is not present in the PQ
  201.      */
  202.     @Override
  203.     public void changePriority(T item, double priority) {
  204.         if (!contains(item)) {
  205.             throw new NoSuchElementException();
  206.         }
  207.         int i = itemsMap.get(item);
  208.         items.get(i).setPriority(priority);
  209.         reposition(i);
  210.     }
  211.  
  212.     /**
  213.      * Returns the number of items in the PQ.
  214.      * Runs in O(log N) time.
  215.      */
  216.     @Override
  217.     public int size() {
  218.         return items.size();
  219.     }
  220.  
  221.     public void print() {
  222.         for (PriorityNode node: items) {
  223.             System.out.println(node.getPriority());
  224.         }
  225.     }
  226. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top