Complete the following class in java all the methods according to the requirements shown in the rubric import jsjf.exceptions.*; /** * LinkedHeap implements a heap. * * @author Java Foundations * @version 4.0 */ public class LinkedHeap extends LinkedBinaryTree implements HeapADT { publicHeapNode lastNode; publicLinkedHeap() { super(); } /** * Adds the specified element to this heap in the appropriate * position according to its key value. * * @param obj the element to be added to the heap */ publicvoidaddElement(Tobj) { HeapNode node = newHeapNode(obj); if (root == null) root=node; else { HeapNode nextParent = getNextParentAdd(); if (nextParent.getLeft() == null) nextParent.setLeft(node); else nextParent.setRight(node); node.setParent(nextParent); } lastNode = node; modCount++; if (size() > 1) heapifyAdd(); } /** * Returns the node that will be the parent of the new node * * @return the node that will be the parent of the new node */ privateHeapNode getNextParentAdd() { HeapNode result = lastNode; while ((result != root) && (result.getParent().getLeft() != result)) result = result.getParent(); if (result != root) if (result.getParent().getRight() == null) result = result.getParent(); else { result = (HeapNode)result.getParent().getRight(); while (result.getLeft() != null) result = (HeapNode)result.getLeft(); } else while (result.getLeft() != null) result = (HeapNode)result.getLeft(); returnresult; } /** * Reorders this heap after adding a node. */ privatevoidheapifyAdd() { Ttemp; HeapNode next = lastNode; temp = next.getElement(); while ((next != root) && (((Comparable)temp).compareTo(next.getParent().getElement()) < 0)) { next.setElement(next.getParent().getElement()); next = next.parent; } next.setElement(temp); } /** * Remove the element with the lowest value in this heap and * returns a reference to it. Throws an EmptyCollectionException * if the heap is empty. * * @return the element with the lowest value in this heap * @throws EmptyCollectionException if the heap is empty */ publicTremoveMin() throwsEmptyCollectionException { if (isEmpty()) thrownewEmptyCollectionException("LinkedHeap"); TminElement = root.getElement(); if (size() == 1) { root = null; lastNode = null; } else { HeapNode nextLast = getNewLastNode(); if (lastNode.getParent().getLeft() == lastNode) lastNode.getParent().setLeft(null); else lastNode.getParent().setRight(null); ((HeapNode)root).setElement(lastNode.getElement()); lastNode = nextLast; heapifyRemove(); } modCount++; returnminElement; } /** * Reorders this heap after removing the root element. */ privatevoidheapifyRemove() { Ttemp; HeapNode node = (HeapNode)root; HeapNode left = (HeapNode)node.getLeft(); HeapNode right = (HeapNode)node.getRight(); HeapNode next; if ((left == null) && (right == null)) next = null; elseif (right == null) next = left; elseif (((Comparable)left.getElement()).compareTo(right.getElement()) < 0) next = left; else next = right; temp = node.getElement(); while ((next != null) && (((Comparable)next.getElement()).compareTo(temp) < 0)) { node.setElement(next.getElement()); node = next; left = (HeapNode)node.getLeft(); right = (HeapNode)node.getRight(); if ((left == null) && (right == null)) next = null; elseif (right == null) next = left; elseif (((Comparable)left.getElement()).compareTo(right.getElement()) < 0) next = left; else next = right; } node.setElement(temp); } /** * Returns the node that will be the new last node after a remove. * * @return the node that will be the new last node after a remove */ privateHeapNode getNewLastNode() { HeapNode result = lastNode; while ((result != root) && (result.getParent().getLeft() == result)) result = result.getParent(); if (result != root) result = (HeapNode)result.getParent().getLeft(); while (result.getRight() != null) result = (HeapNode)result.getRight(); returnresult; } /** * Returns the element with the lowest value in this heap. * Throws an EmptyCollectionException if the heap is empty. * * @return the element with the lowest value in this heap * @throws EmptyCollectionException if the heap is empty */ publicTfindMin() throwsEmptyCollectionException { if (isEmpty()) thrownewEmptyCollectionException("LinkedHeap"); returnroot.getElement(); } }

Complete the following class in java all the methods according to the requirements shown in the rubric import jsjf.exceptions.*; /** * LinkedHeap implements a heap. * * @author Java Foundations * @version 4.0 */ public class LinkedHeap extends LinkedBinaryTree implements HeapADT { publicHeapNode lastNode; publicLinkedHeap() { super(); } /** * Adds the specified element to this heap in the appropriate * position according to its key value. * * @param obj the element to be added to the heap */ publicvoidaddElement(Tobj) { HeapNode node = newHeapNode(obj); if (root == null) root=node; else { HeapNode nextParent = getNextParentAdd(); if (nextParent.getLeft() == null) nextParent.setLeft(node); else nextParent.setRight(node); node.setParent(nextParent); } lastNode = node; modCount++; if (size() > 1) heapifyAdd(); } /** * Returns the node that will be the parent of the new node * * @return the node that will be the parent of the new node */ privateHeapNode getNextParentAdd() { HeapNode result = lastNode; while ((result != root) && (result.getParent().getLeft() != result)) result = result.getParent(); if (result != root) if (result.getParent().getRight() == null) result = result.getParent(); else { result = (HeapNode)result.getParent().getRight(); while (result.getLeft() != null) result = (HeapNode)result.getLeft(); } else while (result.getLeft() != null) result = (HeapNode)result.getLeft(); returnresult; } /** * Reorders this heap after adding a node. */ privatevoidheapifyAdd() { Ttemp; HeapNode next = lastNode; temp = next.getElement(); while ((next != root) && (((Comparable)temp).compareTo(next.getParent().getElement()) < 0)) { next.setElement(next.getParent().getElement()); next = next.parent; } next.setElement(temp); } /** * Remove the element with the lowest value in this heap and * returns a reference to it. Throws an EmptyCollectionException * if the heap is empty. * * @return the element with the lowest value in this heap * @throws EmptyCollectionException if the heap is empty */ publicTremoveMin() throwsEmptyCollectionException { if (isEmpty()) thrownewEmptyCollectionException("LinkedHeap"); TminElement = root.getElement(); if (size() == 1) { root = null; lastNode = null; } else { HeapNode nextLast = getNewLastNode(); if (lastNode.getParent().getLeft() == lastNode) lastNode.getParent().setLeft(null); else lastNode.getParent().setRight(null); ((HeapNode)root).setElement(lastNode.getElement()); lastNode = nextLast; heapifyRemove(); } modCount++; returnminElement; } /** * Reorders this heap after removing the root element. */ privatevoidheapifyRemove() { Ttemp; HeapNode node = (HeapNode)root; HeapNode left = (HeapNode)node.getLeft(); HeapNode right = (HeapNode)node.getRight(); HeapNode next; if ((left == null) && (right == null)) next = null; elseif (right == null) next = left; elseif (((Comparable)left.getElement()).compareTo(right.getElement()) < 0) next = left; else next = right; temp = node.getElement(); while ((next != null) && (((Comparable)next.getElement()).compareTo(temp) < 0)) { node.setElement(next.getElement()); node = next; left = (HeapNode)node.getLeft(); right = (HeapNode)node.getRight(); if ((left == null) && (right == null)) next = null; elseif (right == null) next = left; elseif (((Comparable)left.getElement()).compareTo(right.getElement()) < 0) next = left; else next = right; } node.setElement(temp); } /** * Returns the node that will be the new last node after a remove. * * @return the node that will be the new last node after a remove */ privateHeapNode getNewLastNode() { HeapNode result = lastNode; while ((result != root) && (result.getParent().getLeft() == result)) result = result.getParent(); if (result != root) result = (HeapNode)result.getParent().getLeft(); while (result.getRight() != null) result = (HeapNode)result.getRight(); returnresult; } /** * Returns the element with the lowest value in this heap. * Throws an EmptyCollectionException if the heap is empty. * * @return the element with the lowest value in this heap * @throws EmptyCollectionException if the heap is empty */ publicTfindMin() throwsEmptyCollectionException { if (isEmpty()) thrownewEmptyCollectionException("LinkedHeap"); returnroot.getElement(); } }

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Complete the following class in java all the methods according to the requirements shown in the rubric

import jsjf.exceptions.*;

/**

* LinkedHeap implements a heap.

* @author Java Foundations

* @version 4.0

public class LinkedHeap<T> extends LinkedBinaryTree<T> implements HeapADT<T>

{

publicHeapNode<T> lastNode;

publicLinkedHeap()

{

super();

}

/**

* Adds the specified element to this heap in the appropriate

* position according to its key value.

* @param obj the element to be added to the heap

publicvoidaddElement(Tobj)

{

HeapNode<T> node = newHeapNode<T>(obj);

if (root == null)

root=node;

else

{

HeapNode<T> nextParent = getNextParentAdd();

if (nextParent.getLeft() == null)

nextParent.setLeft(node);

else

nextParent.setRight(node);

node.setParent(nextParent);

}

lastNode = node;

modCount++;

if (size() > 1)

heapifyAdd();

}

/**

* Returns the node that will be the parent of the new node

* @return the node that will be the parent of the new node

privateHeapNode<T> getNextParentAdd()

{

HeapNode<T> result = lastNode;

while ((result != root) && (result.getParent().getLeft() != result))

result = result.getParent();

if (result != root)

if (result.getParent().getRight() == null)

result = result.getParent();

else

{

result = (HeapNode<T>)result.getParent().getRight();

while (result.getLeft() != null)

result = (HeapNode<T>)result.getLeft();

}

else

while (result.getLeft() != null)

result = (HeapNode<T>)result.getLeft();

returnresult;

}

/**

* Reorders this heap after adding a node.

privatevoidheapifyAdd()

{

Ttemp;

HeapNode<T> next = lastNode;

temp = next.getElement();

while ((next != root) &&

(((Comparable<T>)temp).compareTo(next.getParent().getElement()) < 0))

{

next.setElement(next.getParent().getElement());

next = next.parent;

}

next.setElement(temp);

}

/**

* Remove the element with the lowest value in this heap and

* returns a reference to it. Throws an EmptyCollectionException

* if the heap is empty.

* @return the element with the lowest value in this heap

* @throws EmptyCollectionException if the heap is empty

publicTremoveMin() throwsEmptyCollectionException

{

if (isEmpty())

thrownewEmptyCollectionException("LinkedHeap");

TminElement = root.getElement();

if (size() == 1)

{

root = null;

lastNode = null;

}

else

{

HeapNode<T> nextLast = getNewLastNode();

if (lastNode.getParent().getLeft() == lastNode)

lastNode.getParent().setLeft(null);

else

lastNode.getParent().setRight(null);

((HeapNode<T>)root).setElement(lastNode.getElement());

lastNode = nextLast;

heapifyRemove();

}

modCount++;

returnminElement;

}

/**

* Reorders this heap after removing the root element.

privatevoidheapifyRemove()

{

Ttemp;

HeapNode<T> node = (HeapNode<T>)root;

HeapNode<T> left = (HeapNode<T>)node.getLeft();

HeapNode<T> right = (HeapNode<T>)node.getRight();

HeapNode<T> next;

if ((left == null) && (right == null))

next = null;

elseif (right == null)

next = left;

elseif (((Comparable<T>)left.getElement()).compareTo(right.getElement()) < 0)

next = left;

else

next = right;

temp = node.getElement();

while ((next != null) &&

(((Comparable<T>)next.getElement()).compareTo(temp) < 0))

{

node.setElement(next.getElement());

node = next;

left = (HeapNode<T>)node.getLeft();

right = (HeapNode<T>)node.getRight();

if ((left == null) && (right == null))

next = null;

elseif (right == null)

next = left;

elseif (((Comparable<T>)left.getElement()).compareTo(right.getElement()) < 0)

next = left;

else

next = right;

}

node.setElement(temp);

}

/**

* Returns the node that will be the new last node after a remove.

* @return the node that will be the new last node after a remove

privateHeapNode<T> getNewLastNode()

{

HeapNode<T> result = lastNode;

while ((result != root) && (result.getParent().getLeft() == result))

result = result.getParent();

if (result != root)

result = (HeapNode<T>)result.getParent().getLeft();

while (result.getRight() != null)

result = (HeapNode<T>)result.getRight();

returnresult;

}

/**

* Returns the element with the lowest value in this heap.

* Throws an EmptyCollectionException if the heap is empty.

* @return the element with the lowest value in this heap

* @throws EmptyCollectionException if the heap is empty

publicTfindMin() throwsEmptyCollectionException

{

if (isEmpty())

thrownewEmptyCollectionException("LinkedHeap");

returnroot.getElement();

}

# Linked Heap Project

## Criteria

- **Documentation**

- **Implement HeapDriver Program**
- Presents menu and calls methods in the interface.

- **Implement Peek Method**
- Displays the current root element. This does not remove the element.

- **Implement the Display Method**
- Displays all elements in the heap.

- **Implement the Height Method**
- Returns the height of the current heap.

- **Implement Additional Methods Necessary to Support the Functionality Required**

- **Successful Run**

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.