heap
Class MyLinkedHeapTree<E>

java.lang.Object
  net.datastructures.LinkedBinaryTree<E>
      heap.MyLinkedHeapTree<E>

All Implemented Interfaces:

BinaryTree<E>, CompleteBinaryTree<E>, Tree<E>

public class MyLinkedHeapTree<E>
extends LinkedBinaryTree<E>
implements CompleteBinaryTree<E>

An implementation of a complete binary tree by means of a linked structure. The LinkedBinaryTree class takes care of most of the "mechanics" of modifying the tree, but you will need to think about how to implement a CompleteBinaryTree such that additions and removals operate *only* on the last node. You must also ensure that whatever method you choose for tracking nodes within the tree, running time requirements for the assignment are not violated. Feel free to add additional comments.

Field Summary

Fields inherited from class net.datastructures.LinkedBinaryTree

root, size

Constructor Summary

MyLinkedHeapTree()
Default constructor.

Method Summary

Position<E>	add(E element) Adds an element to the tree just after the last node.
E	remove() Removes and returns the element stored in the last node of the tree.

Methods inherited from class net.datastructures.LinkedBinaryTree

addRoot, attach, checkPosition, children, createNode, expandExternal, hasLeft, hasRight, inorderPositions, insertLeft, insertRight, isEmpty, isExternal, isInternal, isRoot, iterator, left, parent, positions, preorderPositions, remove, removeAboveExternal, replace, right, root, sibling, size, swapElements

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.datastructures.BinaryTree

hasLeft, hasRight, left, right

Methods inherited from interface net.datastructures.Tree

children, isEmpty, isExternal, isInternal, isRoot, iterator, parent, positions, replace, root, size

Constructor Detail

MyLinkedHeapTree

public MyLinkedHeapTree()

Default constructor. The tree begins empty.

Method Detail

add

public Position<E> add(E element)

Adds an element to the tree just after the last node. Returns the newly created position for the element. This method must run in at least *amortized* O(1) time, although a worst-case running time of O(log n) is permissible. There are multiple ways you can implement this method, and it *is* possible to achieve a constant O(1) worst-case running time! See the design section of the handout for more information, and check with the textbook or a TA if you are unsure of the distinction between amortized O(1) time and worst-case O(1).

Specified by:

add in interface CompleteBinaryTree<E>

Parameters:

element - to be added to the tree as the new last node

Returns:

the Position of the newly inserted element

remove

public E remove()
         throws EmptyTreeException

Removes and returns the element stored in the last node of the tree. This method must run in at least *amortized* O(1) time, although a worst-case running time of O(log n) is permissible. There are multiple ways you can implement this method, and it *is* possible to achieve a constant O(1) worst-case running time! See the design section of the handout for more information, and check with the textbook or a TA if you are unsure of the distinction between amortized O(1) time and worst-case O(1).

Specified by:

remove in interface CompleteBinaryTree<E>

Returns:

the element formerly stored in the last node (prior to its removal)

Throws:

EmptyTreeException - if the tree is empty and no last node exists