Question

Complete HeapPriorityQueue (7 points). In lecture we implemented HeapPriorityQueue using an array-based representation of a heap (a complete binary tree whose entries satisfy the heap-order property). For this problem, complete the included HeapPriorityQueue class by using the LinkedBinaryTree class to represent a heap. Hint: the most challenging part of this problem is identifying the last Position in the heap and the next available Position in the heap. It is suggested that you review the array-based heap to better understand how these positions can be located. You need not concern yourself with the runtimes of your solutions. [Note that the names of these classes are the same because they both utilize heaps, just heaps implemented differently.]

///HeapPriorityQueue

package cs313final;

import java.util.Comparator;

/*
* Complete this file for part 2 of the assignment
* Note that this class shares the same name as the class from lecture,
* but is to be implemented using a LinkedBinaryTree heap
*
* No additional classes should be imported
*/

public class HeapPriorityQueue<K,V> extends AbstractPriorityQueue<K,V> {

}

////LinkedBinaryTree

package cs313final;

/*
* This file should not be modified
*/

public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {

   protected static class Node<E> implements Position<E> {
      
       private E element;
       private Node<E> parent, left, right;
      
       public Node(E e, Node<E> p, Node<E> l, Node<E> r) {
           this.element = e;
           this.parent = p;
           this.left = l;
           this.right = r;
       }

       public E getElement() {
           return element;
       }

       public void setElement(E element) {
           this.element = element;
       }

       public Node<E> getParent() {
           return parent;
       }

       public void setParent(Node<E> parent) {
           this.parent = parent;
       }

       public Node<E> getLeft() {
           return left;
       }

       public void setLeft(Node<E> left) {
           this.left = left;
       }

       public Node<E> getRight() {
           return right;
       }

       public void setRight(Node<E> right) {
           this.right = right;
       }
      
   }
  
   protected Node<E> root;
   private int size;
  
   public LinkedBinaryTree() {
       this.root = null;
       this.size = 0;
   }
  
   protected Node<E> createNode(E e, Node<E> p, Node<E> l, Node<E> r) {
       return new Node<>(e, p, l, r);
   }
  
   protected Node<E> validate(Position<E> p) {
       if (!(p instanceof Node)) throw new IllegalArgumentException("Position is not valid type");
       Node<E> node = (Node<E>) p;
       if (node.getParent() == node) throw new IllegalArgumentException("Position is no longer in the tree");
       return node;
   }
  
   @Override
   public Position<E> left(Position<E> p) {
       Node<E> node = this.validate(p);
       return node.getLeft();
   }

   @Override
   public Position<E> right(Position<E> p) {
       Node<E> node = this.validate(p);
       return node.getRight();
   }

   @Override
   public Position<E> root() {
       return this.root;
   }

   @Override
   public Position<E> parent(Position<E> p) {
       Node<E> node = this.validate(p);
       return node.getParent();
   }

   @Override
   public int size() {
       return size;
   }
  
   public Position<E> addRoot(E e) throws IllegalStateException {
       if (!this.isEmpty()) throw new IllegalStateException("Tree is not empty");
       this.root = this.createNode(e, null, null, null);
       this.size = 1;
       return this.root;
   }

   public Position<E> addLeft(Position<E> p, E e) {
       Node<E> node = this.validate(p);
       if (node.getLeft() != null) throw new IllegalStateException("Position already has a left child");
       Node<E> child = this.createNode(e, node, null, null);
       node.setLeft(child);
       this.size++;
       return child;
   }
  
   public Position<E> addRight(Position<E> p, E e) {
       Node<E> node = this.validate(p);
       if (node.getRight() != null) throw new IllegalStateException("Position already has a right child");
       Node<E> child = this.createNode(e, node, null, null);
       node.setRight(child);
       this.size++;
       return child;
   }
  
   public E set(Position<E> p, E e) {
       Node<E> node = this.validate(p);
       E old = node.getElement();
       node.setElement(e);
       return old;
   }
  
   public void attach(Position<E> p, LinkedBinaryTree<E> t1, LinkedBinaryTree<E> t2) {
       Node<E> node = this.validate(p);
       if (this.isInternal(p)) throw new IllegalStateException("Position must be a leaf");
      
       if (t1 != null) {
           this.size += t1.size();
          
           t1.root.setParent(node);
           node.setLeft(t1.root);
          
           t1.root = null;
           t1.size = 0;
       }
       if (t2 != null) {
           this.size += t2.size();
          
           t2.root.setParent(node);
           node.setRight(t2.root);
          
           t2.root = null;
           t2.size = 0;
       }
   }
  
   public E remove(Position<E> p) {
       Node<E> node = this.validate(p);
       if (this.numChildren(p) == 2) throw new IllegalStateException("Position has two children");
      
       Node<E> child;
       if (node.getLeft() != null)
           child = node.getLeft();
       else
           child = node.getRight();
      
       if (child != null)
           child.setParent(node.getParent());
      
       if (node == this.root)
           this.root = child;
       else {
           Node<E> parent = node.getParent();
           if (node == parent.getLeft())
               parent.setLeft(child);
           else
               parent.setRight(child);
       }
      
       this.size--;
      
       E old = node.getElement();
       node.setElement(null);
       node.setLeft(null);
       node.setRight(null);
       node.setParent(node);
       return old;
   }
  
   //example usage
   public static void main(String[] args) {
      
       //initialize empty tree
       LinkedBinaryTree<String> tree = new LinkedBinaryTree<>();
      
       Position<String> root = tree.addRoot("I'm the data at the root node");
      
       Position<String> p = tree.addLeft(root, "I'm the data at the left child of the root");
      
       System.out.println(tree.isExternal(p));
      
       LinkedBinaryTree<String> t1 = new LinkedBinaryTree<>();
       Position<String> r1 = t1.addRoot("t1 root");
       t1.addRight(r1, "t1 right child");
      
       tree.attach(p, t1, null);
      
       p = tree.left(p); //now at "t1 root"
       p = tree.right(p); //now at "t1 right child"
      
       System.out.println(p.getElement());
      
       System.out.println(tree);
   }
  
}

///Position

package cs313final;

/*
* This file should not be modified
*/

public interface Position<E> {

   E getElement();
  
}

Answer 1

/** * HeapPriorityQueue uses the interface PriorityQueue, to implement * the priority queue by means of a heap. */ public class HeapPriorityQueue implements PriorityQueue { private LinkedBinaryTree tree; // the binary tree to be a LinkedBinaryTree private Position lastLeaf; // the last leaf in the tree private Comparator comparator; // means of comparing keys /** Constructor * @param Comparator A comparator for comparing keys */ public HeapPriorityQueue(Comparator comp) { comparator = comp; tree = new LinkedBinaryTree(); lastLeaf = null; } /** insertItem inserts an element into the heap in correct order * @param key the comparable key * @param element the value associated with the key * @return void */ public void insert(Object key, Object element) throws InvalidKeyException { if (! comparator.isComparable(key)) throw new InvalidKeyException("Invalid Key Type"); Position z; // insertion position if (isEmpty()) z = tree.root(); else { z = lastLeaf; while (! tree.isRoot(z) && (! isLeftChild(z))) z = tree.parent(z); if (! tree.isRoot(z)) z = tree.rightChild(tree.parent(z)); while (! tree.isExternal(z)) z = tree.leftChild(z); } tree.expandExternal(z); tree.replace(z, new Item(key,element)); lastLeaf = z; Position u; while (! tree.isRoot(z)) { // up-heap bubbling u = tree.parent(z); if (comparator.isLessThanOrEqualTo(keyOfPosition(u), keyOfPosition(z))) break; tree.swap(u,z); z = u; } } // end insertItem() /** * keyOfPosition obtains the key associated with the position * @param p a position object * @return Object the key * @throws InvalidPositionException */ private Object keyOfPosition(Position p) throws InvalidPositionException { return ((Item) p.element()).key(); // cast should not fail } /** * elementOfPosition obtains the element associated with the position * @param p a position object * @return Object the element * @throws InvalidPositionException */ private Object elementOfPosition(Position p) throws InvalidPositionException { return ((Item) p.element()).element(); } /** * isLeftChild returns the left child of a position, or throws * an exception if there is no left child * @param p a position * @return boolean * @throws InvalidPositionException */ private boolean isLeftChild(Position p) throws InvalidPositionException { try { return tree.leftChild(tree.parent(p)).equals(p); } catch(BoundaryViolationException e) { return false; } } /** * isRightChild returns the right child of a position, or throws * an exception if there is no left child * @param p a position * @return boolean * @throws InvalidPositionException */ private boolean isRightChild(Position p) throws InvalidPositionException { try { return tree.rightChild(tree.parent(p)).equals(p); } catch(BoundaryViolationException e) { return false; } } // PriorityQueue interface methods /** * size returns the number of elements in the tree * @param none * @returns int */ public int size() { return tree.size() - 1; } /** * isEmpty returns true if the tree is empty, else false * @param none * @return boolean */ public boolean isEmpty() { return (size() == 0); } /** * min returns the minimum element in the tree (does not remove) * @param none * @return Object the element contained in the tree * @throws EmptyContainerException */ public Object min() throws EmptyContainerException { if (isEmpty()) throw new EmptyContainerException("No root in tree"); return ((Item)((Node)tree.root()).element()).element(); } /** * minKey returns the smallest key in the tree (does not remove) * @param none * @return Object the key contained in the tree * @throws EmptyContainerException */ public Object minKey() throws EmptyContainerException { if (isEmpty()) throw new EmptyContainerException("No root in tree"); return ((Item)((Node)tree.root()).element()).key(); } /** * removeMin removes the minimum element from the tree * get data from root, replace root with last element, heapify * @param none * @return Object the minimum element * @throws EmptyContainerException */ public Object removeMin() throws EmptyContainerException { if (isEmpty()) throw new EmptyContainerException("Tree is empty"); Object min = min(); Position r = tree.root(); Position tempLast = lastLeaf; if (! tree.isRoot(lastLeaf)) { tree.replace(r,lastLeaf.element()); while (! tree.isRoot(lastLeaf) && isLeftChild(lastLeaf)) { lastLeaf = tree.parent(lastLeaf); } if (! tree.isRoot(lastLeaf)) { lastLeaf = tree.leftChild(tree.parent(lastLeaf)); } while (! tree.isExternal(tree.rightChild(lastLeaf))) { lastLeaf = tree.rightChild(lastLeaf); } } tree.removeAboveExternal(tree.rightChild(tempLast)); while (! tree.isExternal(r)) { Position w; if ( tree.isExternal(tree.rightChild(r)) && tree.isExternal(tree.leftChild(r)) ) { break; } else if ( tree.isExternal(tree.rightChild(r)) && (! tree.isExternal(tree.leftChild(r))) ) { w = tree.leftChild(r); } else { if ( comparator.isLessThan(keyOfPosition(tree.leftChild(r)), keyOfPosition(tree.rightChild(r))) ) { w = tree.leftChild(r); } else { w = tree.rightChild(r); } } if ( comparator.isGreaterThanOrEqualTo(keyOfPosition(r), keyOfPosition(w)) ) { tree.swap(r,w); r = w; } else break; } // end while return min; } } // end class HeapPriorityQueue