Advertisement
Guest User

Untitled

a guest
Mar 18th, 2019
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.22 KB | None | 0 0
  1. package bearmaps;
  2.  
  3.  
  4. import java.util.ArrayList;
  5. import java.util.HashMap;
  6. import java.util.NoSuchElementException;
  7.  
  8.  
  9. public class ArrayHeapMinPQ<T> implements ExtrinsicMinPQ<T> {
  10.     private HashMap<T, Integer> index;
  11.     private ArrayList<PriorityNode> arrayHeap;
  12.     private int size;
  13.  
  14.     public ArrayHeapMinPQ() {
  15.         arrayHeap = new ArrayList<>();
  16.         index = new HashMap<>();
  17.         size = 0;
  18.     }
  19.  
  20.     public ArrayHeapMinPQ(int capacity) {
  21.         if (capacity <= 0) {
  22.             throw new IndexOutOfBoundsException("Capacity must be greater than zero!");
  23.         }
  24.         arrayHeap = new ArrayList<>(capacity + 1);
  25.         index = new HashMap<>(capacity + 1);
  26.         size = 0;
  27.     }
  28.  
  29.  
  30.     /* Adds an item with the given priority value. Throws an
  31.      * IllegalArgumentException if item is already present.
  32.      * You may assume that item is never null. */
  33.     @Override
  34.     public void add(T item, double priority) {
  35.         if (contains(item)) {
  36.             throw new IllegalArgumentException("This item already exists!");
  37.         }
  38.         arrayHeap.set(this.size + 1, new PriorityNode(item, priority));
  39.         index.put(item, this.size + 1);
  40.         swim(this.size + 1);
  41.         size++;
  42.     }
  43.  
  44.     /* Returns true if the PQ contains the given item. */
  45.     @Override
  46.     public boolean contains(T item) {
  47.         return index.containsKey(item);
  48.  
  49.     }
  50.  
  51.     /* Returns the minimum item. Throws NoSuchElementException if the PQ is empty. */
  52.     @Override
  53.     public T getSmallest() {
  54.         if (size == 0) {
  55.             throw new NoSuchElementException("The queue is currently empty!");
  56.         }
  57.         return arrayHeap.get(1).item;
  58.  
  59.     }
  60.  
  61.     /* Removes and returns the minimum item. Throws NoSuchElementException if the PQ is empty. */
  62.     @Override
  63.     public T removeSmallest() {
  64.         if (size == 0) {
  65.             throw new NoSuchElementException("The queue is currently empty!");
  66.         }
  67.         T save = getSmallest();
  68.         swap(1, size);
  69.         index.remove(arrayHeap.get(size).item);
  70.         arrayHeap.set(size, null);
  71.         sink(1);
  72.         size--;
  73.         return save;
  74.  
  75.  
  76.     }
  77.  
  78.     /* Returns the number of items in the PQ. */
  79.     @Override
  80.     public int size() {
  81.         return size;
  82.     }
  83.  
  84.     /* Changes the priority of the given item. Throws NoSuchElementException if the item
  85.      * doesn't exist. */
  86.  
  87.     @Override
  88.     public void changePriority(T item, double priority) {
  89.         if (!contains(item)) {
  90.             throw new NoSuchElementException("This item does not exist!");
  91.         }
  92.         double origPriority = arrayHeap.get(index.get(item)).priority;
  93.         arrayHeap.get(index.get(item)).priority = priority;
  94.         if (origPriority > priority) {
  95.             swim(index.get(item));
  96.         }
  97.         if (origPriority < priority) {
  98.             sink(index.get(item));
  99.         }
  100.  
  101.     }
  102.  
  103.     private class PriorityNode {
  104.         private T item;
  105.         private double priority;
  106.  
  107.         PriorityNode(T e, double p) {
  108.             this.item = e;
  109.             this.priority = p;
  110.         }
  111.     }
  112.  
  113. //  Helper methods:
  114.  
  115.     private void swap(int a, int b) {
  116. //        a and b = index values
  117.         PriorityNode save = arrayHeap.get(a);
  118.         arrayHeap.set(a, arrayHeap.get(b));
  119.         arrayHeap.set(b, save);
  120. //            set index in HashMap
  121.         index.put(arrayHeap.get(a).item, a);
  122.         index.put(arrayHeap.get(b).item, b);
  123.  
  124.     }
  125.  
  126.     private int parent(int k) {
  127.         return (k - 1) / 2;
  128.     }
  129.  
  130.     private void swim(int k) {
  131.         int parent = parent(k);
  132.         if (k > 1 && arrayHeap.get(parent).priority > arrayHeap.get(k).priority) {
  133.             swap(k, parent);
  134.             swim(parent);
  135.         }
  136.     }
  137.  
  138.     private int leftChild(int k) {
  139.         return k * 2;
  140.     }
  141.  
  142.     private int rightChild(int k) {
  143.         return k * 2 + 1;
  144.     }
  145.  
  146.     private void sink(int k) {
  147.         int leftChild = leftChild(k);
  148.         int rightChild = rightChild(k);
  149.         if (arrayHeap.get(rightChild) != null
  150.                 && arrayHeap.get(rightChild).priority < arrayHeap.get(k).priority) {
  151.             swap(rightChild, k);
  152.             sink(k);
  153.         } else if (arrayHeap.get(leftChild) != null
  154.                 && arrayHeap.get(leftChild).priority < arrayHeap.get(k).priority) {
  155.             swap(leftChild, k);
  156.             sink(k);
  157.         }
  158.     }
  159. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement