Class Heap<E extends java.lang.Comparable<? super E>>

java.lang.Object

Heap<E>

All Implemented Interfaces:

IPriorityQueue<E>, IQueue<E>

public class Heap<E extends java.lang.Comparable<? super E>>
extends java.lang.Object
implements IPriorityQueue<E>

A min-heap data structure and a heap-sort static method. Maintaining the heap property means that when comparing parent and child elements, parent.compareTo(child) <= 0 should be true. Hence, the first element to come out of a heap would be the first element in a sorted list of the elements in the heap (barring ties in priority). Same with the second element, the third element, and so on to the last. Written by cspfrederick and garethhalladay

Constructor Summary

Constructors

Constructor	Description
Heap()	Initializes a newly created Heap object.
Heap(java.util.Collection<E> elems)	Create a heap from the given elements.

Method Summary

Modifier and Type	Method	Description
void	clear()	Remove all elements from this heap.
boolean	contains(java.lang.Object o)	Determine if this heap contains a given element.
void	debugHeap()	A method to help you debug your Heap class.
static <E extends java.lang.Comparable<? super E>> java.util.ArrayList<E>	heapSorted(java.util.ArrayList<E> elems)	Return a sorted list of the elements of the elems collection.
(package private) boolean	isLeaf(int i)	Tests if the current index is a leaf in the tree
(package private) static int	lchild(int i)	Returns the index of the left child
static void	main(java.lang.String[] args)
boolean	offer(E e)	Store the given element in this heap.
static void	outtakes()
(package private) static int	parent(int i)	Returns the index of the parent node.
E	peek()	Return (but don't remove) a most priority element from this heap.
E	poll()	Remove and return a most priority element from this heap.
(package private) int	priorityChild(int i)	Returns the index of a most priority child of a particular node.
(package private) static int	rchild(int i)	Returns the index of the right child
int	size()	Return the number of elements stored in this heap.
(package private) void	swapDown(int i)	Takes the element at position i and swaps it down the tree with its largest child, repeatedly, until the heap property is restored.
(package private) void	swapUp(int i)	Performs the swapUp operation to place a newly inserted element in its correct place so that the heap maintains the heap property.
java.lang.String	toString()	Returns a string representation of this queue.

Methods inherited from interface IPriorityQueue

add, element, isEmpty, remove

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

Heap

public Heap()

Initializes a newly created Heap object.

Look above... is your variable instantiated? Well, you'd better do that here.

Heap

public Heap(java.util.Collection<E> elems)

Create a heap from the given elements.

Repeated calls to offer would be a correct implementation. Instead uses an algorithm that runs in time linear to the number of elements. This is a small (but neat!) efficiency.

Parameters:

elems - the elements that will initially populate the heap

Method Detail

main

public static void main(java.lang.String[] args)

outtakes

public static void outtakes()

parent

static int parent(int i)

Returns the index of the parent node.

Parameters:

i - the current index

Returns:

the index of the parent

lchild

static int lchild(int i)

Returns the index of the left child

Parameters:

i - the current index

Returns:

the index of the left child

rchild

static int rchild(int i)

Returns the index of the right child

Parameters:

i - the current index

Returns:

the index of the right child

isLeaf

boolean isLeaf(int i)

Tests if the current index is a leaf in the tree

Parameters:

i - the current index

Returns:

true if the index belongs to a leaf node, false otherwise (an internal node).

priorityChild

int priorityChild(int i)

Returns the index of a most priority child of a particular node. If a node has just one child, that is most priority. Otherwise, the left child is most priority if left.compareTo(right) <= 0, or else the right is most priority.

the index of the left child lchild(int) the index of the right child rchild(int)

Parameters:

i - the current index

Returns:

the index of the child with the highest priority

swapDown

void swapDown(int i)

Takes the element at position i and swaps it down the tree with its largest child, repeatedly, until the heap property is restored.

While the current index does not represent a leaf, compare the child of greatest priority to the current element. If the element in the child node is higher priority, swap it with the parent. Repeat as necessary.

Parameters:

i - the index of the current element

swapUp

void swapUp(int i)

Performs the swapUp operation to place a newly inserted element in its correct place so that the heap maintains the heap property.

While the current element is not the root, compare it with its parent element. If it is of greater priority, then swap the elements. Repeat as necessary.

Parameters:

i - the index of the current element

offer

public boolean offer(E e)

Store the given element in this heap.

Specified by:

offer in interface IPriorityQueue<E extends java.lang.Comparable<? super E>>

Specified by:

offer in interface IQueue<E extends java.lang.Comparable<? super E>>

Parameters:

e - the element to add

Returns:

true (since a Heap is unbounded, and false would mean it didn't have room)

poll

public E poll()

Remove and return a most priority element from this heap.

Specified by:

poll in interface IPriorityQueue<E extends java.lang.Comparable<? super E>>

Specified by:

poll in interface IQueue<E extends java.lang.Comparable<? super E>>

Returns:

null if empty, else a most priority element

peek

public E peek()

Return (but don't remove) a most priority element from this heap.

Specified by:

peek in interface IPriorityQueue<E extends java.lang.Comparable<? super E>>

Specified by:

peek in interface IQueue<E extends java.lang.Comparable<? super E>>

Returns:

null if empty, else a most priority element

size

public int size()

Return the number of elements stored in this heap.

Specified by:

size in interface IQueue<E extends java.lang.Comparable<? super E>>

Returns:

the size of the heap

clear

public void clear()

Remove all elements from this heap. After, it is empty.

Specified by:

clear in interface IQueue<E extends java.lang.Comparable<? super E>>

contains

public boolean contains(java.lang.Object o)

Determine if this heap contains a given element.

Specified by:

contains in interface IQueue<E extends java.lang.Comparable<? super E>>

Parameters:

o - object to be checked for containment in this queue

Returns:

true if it is contained, false otherwise

heapSorted

public static <E extends java.lang.Comparable<? super E>> java.util.ArrayList<E> heapSorted(java.util.ArrayList<E> elems)

Return a sorted list of the elements of the elems collection. This method is implemented by the heap sort algorithm: build a heap, extract all elements.

Type Parameters:

E - element type to be sorted

Parameters:

elems - Source collection of elements

Returns:

sorted list of original elements

toString

public java.lang.String toString()

Description copied from interface: IQueue

Returns a string representation of this queue. The string representation consists of a list of the queue's elements in the order they are returned by its iterator, enclosed in square brackets ("[]"). Adjacent elements are separated by the characters ", " (comma and space). Elements are converted to strings as by String.valueOf(Object).

Specified by:

toString in interface IQueue<E extends java.lang.Comparable<? super E>>

Overrides:

toString in class java.lang.Object

Returns:

a string representation of this queue

debugHeap

public void debugHeap()

A method to help you debug your Heap class. This will loop through your array and print out each node with the corresponding child nodes.