CSci 2101: Priority Heaps

Starting code for PriorityQueueHeap:


import java.util.ArrayList;
import java.util.Iterator;

/**
 * 
 * The class implements a min-priority queue, i.e. smaller numbers have higher
 * priority. For instance, if the queue contains 2, 4, 1, then 1 is returned
 * first, then 2, then 4. The smallest element in the queue is called the head
 * of the queue. If the queue contains several elements with the same minimal
 * value, any one of them may play the role of the head.
 * 
 * Elements inserted in the the queue must implement Comparable interface. They
 * are ordered based on the ordering determined by their compareTo method.
 * 
 * The class employs a heap-based implementation, i.e. add and remove are
 * guaranteed to work in O(log(n)) time.
 * 
 * The queue is iterable. However, there are no guarantees on the order of the
 * elements, i.e. they are in general not sorted.
 * 
 * @param <E>
 *            - type of elements in the queue. Must implement Comparable<E>
 */
public class PriorityQueueHeap<E extends Comparable<E>> implements OurQueue<E>,
		Iterable<E> {
	private ArrayList<E> elements = new ArrayList<E>();

	/**
	 * Returns true if this list contains no elements, false otherwise Runs in
	 * constant time.
	 * 
	 * @return true if this list contains no elements, false otherwise
	 */
	public boolean isEmpty() {
		return false;
	}

	/**
	 * Returns the number of elements in this queue. Runs in constant time.
	 * 
	 * @return the number of elements in this queue
	 */
	public int size() {
		return 0;
	}

	/**
	 * Inserts the specified element at its position in the priority queue. The
	 * position is determined by compareTo method: the element e is placed after
	 * all queue elements that are smaller than e based on compareTo and before
	 * all elements that are >= e. Runs in at most log N time where N is the
	 * number of elements currently in the queue.
	 * 
	 * @param e
	 *            - the element to be added to the queue
	 * @throws NullPointerException
	 *             - if the specified element is null
	 */
	public void add(E e) {

	}

	/**
	 * Retrieves and removes the head of this queue. Runs in at most log N time
	 * where N is the number of elements currently in the queue. Throws:
	 * NoSuchElementException - if this queue is empty
	 * 
	 * @return - the head of the queue
	 */
	public E remove() {
		return null;
	}

	/**
	 * Retrieves but does not remove the head of this queue. Runs in constant
	 * time. Throws: NoSuchElementException - if this queue is empty
	 * 
	 * @return - the head of the queue
	 */
	public E element() {
		return null;
	}

	/**
	 * Removes all elements from the queue. This queue will be empty after this
	 * call returns.
	 * 
	 * @return
	 */
	public void clear() {

	}

	/**
	 * Returns an iterator for the queue. There are no guarantees on the order
	 * of the elements, i.e. they are in general not sorted.
	 */
	public Iterator<E> iterator() {
		return elements.iterator();
	}

	// swaps elements at indices i and j
	// to-do: think about checking error conditions
	private void swap(int i, int j) {

	}

	// returns the index of the parent of this node
	// to-do: think about the behavior for the root
	private int parent(int i) {
		return 0;
	}

	// returns the index of the left child of this node
	// to-do: think about the behavior if no such child
	private int leftChild(int i) {
		return 0;
	}

	// returns the index of the right child of this node
	// to-do: think about the behavior if no such child
	private int rightChild(int i) {
		return 0;
	}
}


CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.