Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package bearmaps;
- import java.util.ArrayList;
- import java.util.HashMap;
- import java.util.NoSuchElementException;
- public class ArrayHeapMinPQ<T> implements ExtrinsicMinPQ<T> {
- private HashMap<T, Integer> index;
- private ArrayList<PriorityNode> arrayHeap;
- private int size;
- public ArrayHeapMinPQ() {
- arrayHeap = new ArrayList<>();
- index = new HashMap<>();
- size = 0;
- }
- public ArrayHeapMinPQ(int capacity) {
- if (capacity <= 0) {
- throw new IndexOutOfBoundsException("Capacity must be greater than zero!");
- }
- arrayHeap = new ArrayList<>(capacity + 1);
- index = new HashMap<>(capacity + 1);
- size = 0;
- }
- /* Adds an item with the given priority value. Throws an
- * IllegalArgumentException if item is already present.
- * You may assume that item is never null. */
- @Override
- public void add(T item, double priority) {
- if (contains(item)) {
- throw new IllegalArgumentException("This item already exists!");
- }
- arrayHeap.set(this.size + 1, new PriorityNode(item, priority));
- index.put(item, this.size + 1);
- swim(this.size + 1);
- size++;
- }
- /* Returns true if the PQ contains the given item. */
- @Override
- public boolean contains(T item) {
- return index.containsKey(item);
- }
- /* Returns the minimum item. Throws NoSuchElementException if the PQ is empty. */
- @Override
- public T getSmallest() {
- if (size == 0) {
- throw new NoSuchElementException("The queue is currently empty!");
- }
- return arrayHeap.get(1).item;
- }
- /* Removes and returns the minimum item. Throws NoSuchElementException if the PQ is empty. */
- @Override
- public T removeSmallest() {
- if (size == 0) {
- throw new NoSuchElementException("The queue is currently empty!");
- }
- T save = getSmallest();
- swap(1, size);
- index.remove(arrayHeap.get(size).item);
- arrayHeap.set(size, null);
- sink(1);
- size--;
- return save;
- }
- /* Returns the number of items in the PQ. */
- @Override
- public int size() {
- return size;
- }
- /* Changes the priority of the given item. Throws NoSuchElementException if the item
- * doesn't exist. */
- @Override
- public void changePriority(T item, double priority) {
- if (!contains(item)) {
- throw new NoSuchElementException("This item does not exist!");
- }
- double origPriority = arrayHeap.get(index.get(item)).priority;
- arrayHeap.get(index.get(item)).priority = priority;
- if (origPriority > priority) {
- swim(index.get(item));
- }
- if (origPriority < priority) {
- sink(index.get(item));
- }
- }
- private class PriorityNode {
- private T item;
- private double priority;
- PriorityNode(T e, double p) {
- this.item = e;
- this.priority = p;
- }
- }
- // Helper methods:
- private void swap(int a, int b) {
- // a and b = index values
- PriorityNode save = arrayHeap.get(a);
- arrayHeap.set(a, arrayHeap.get(b));
- arrayHeap.set(b, save);
- // set index in HashMap
- index.put(arrayHeap.get(a).item, a);
- index.put(arrayHeap.get(b).item, b);
- }
- private int parent(int k) {
- return (k - 1) / 2;
- }
- private void swim(int k) {
- int parent = parent(k);
- if (k > 1 && arrayHeap.get(parent).priority > arrayHeap.get(k).priority) {
- swap(k, parent);
- swim(parent);
- }
- }
- private int leftChild(int k) {
- return k * 2;
- }
- private int rightChild(int k) {
- return k * 2 + 1;
- }
- private void sink(int k) {
- int leftChild = leftChild(k);
- int rightChild = rightChild(k);
- if (arrayHeap.get(rightChild) != null
- && arrayHeap.get(rightChild).priority < arrayHeap.get(k).priority) {
- swap(rightChild, k);
- sink(k);
- } else if (arrayHeap.get(leftChild) != null
- && arrayHeap.get(leftChild).priority < arrayHeap.get(k).priority) {
- swap(leftChild, k);
- sink(k);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement