Create a class called MinHeap. Because elements need to be stored in a sorted ma
ID: 3807857 • Letter: C
Question
Create a class called MinHeap. Because elements need to be stored in a sorted manner, you can assume that any elements added to the tree implement the Comparable class with the appropriate generic type (see Binary Search Tree activity for more information):
Can you please complete and put together the following JAVA code:
Main Method:
public static void main(String[] arg){
MinHeapmh=new MinHeap();
mh.insert(2);
mh.insert(4);
mh.insert(1);
mh.insert(10);
mh.insert(3);
mh.insert(6);
mh.insert(15);
mh.insert(12);
mh.insert(16);
mh.insert(5);
while(!mh.isEmpty()){
System.out.println(mh.remove());
}
public class MinHeap >
{
private E[] heap;
private int size = 0;
private static final int DEFAULT_CAPACITY = 8;
public MinHeap(int capacity)
{
heap = (E[]) new Comparable[capacity];
}
public MinHeap()
{
this(DEFAULT_CAPACITY);
}
public int size()
{
return _____;
}
public boolean isEmpty()
{
return size() == _____;
}
private void expand()
{
E[] newHeap = (E[]) new Comparable[heap.length * 2];
for (int i = 0; i < size(); i++)
{
newHeap[i] = heap[i];
}
heap = newHeap;
}
private void swapElements(int p1, int p2)
{
E temp = heap[p1];
heap[p1] = heap[p2];
heap[p2] = temp;
}
private int getParentIndex(int childIndex)
{
// if odd, child is a left node
if (childIndex % 2 != 0) {
return childIndex / 2;
}
// if even, child is a right node
else
{
return childIndex / 2 - 1;
}
}
public void insert(E element)
{
int position = size();
if (position == heap.length)
{
expand();
}
size++;
heap[position] = element;
int parent = getParentIndex(position);
while (position > 0 && heap[position].compareTo(heap[parent]) < 0)
{
// if parent is greater, swap parent and node
swapElements(________, position);
// update position of the new element and find next parent up
position = getParentIndex(position);
parent = getParentIndex(________);
}
}
public E remove()
{
if (isEmpty())
{
return null;
}
// take out root and place last node at root position
E min = heap[0];
heap[____] = heap[size() - 1];
heap[size() - 1] = null; // optional
size--;
// position of new root and its smaller child
int position = 0;
int smallerChild = smallerChildIndex(position);
// while there is a smaller child, swap parent and child
while (__________ != position) {
swapElements(position, smallerChild);
// update position of node and get new smaller child
position = smallerChild;
smallerChild = smallerChildIndex(_______);
}
return min;
}
}
Method for finding the smaller child element:
private int smallerChildIndex(int getParentIndex) {
int smaller = getParentIndex;
// get left child index
int leftChild = 2 * getParentIndex + 1;
// if the left child index is in bounds of the heap...
if (leftChild < size() - 1) {
// set smaller to left if left is smaller than parent
smaller = heap[leftChild].compareTo(heap[smaller]) < 0
? leftChild : smaller;
// get right child index
int rightChild = 2 * getParentIndex + 2;
// if the right child index is in bounds of the heap...
if (rightChild < size() - 1) {
// set smaller to right if right is smaller than parent
smaller = heap[rightChild].compareTo(heap[smaller]) < 0
? rightChild : smaller;
}
}
return smaller;
}
Input: 7, 3, 6, 2, 9, 1, 10, 4
What does the heap look like after all of the elements are added?
How many 'swap' operations must be performed when the value 1 is added (underlined above)?
if a remove operation is performed, which element initially becomes the root? Which children must it be swapped with (in order), to be placed in the correct position?
Explanation / Answer
def find_min(self): # Gets minimum node in a subtree
current_node = self
while current_node.left_child:
current_node = current_node.left_child
return current_node
def replace_node_in_parent(self, new_value=None):
if self.parent:
if self == self.parent.left_child:
self.parent.left_child = new_value
else:
self.parent.right_child = new_value
if new_value:
new_value.parent = self.parent
def binary_tree_delete(self, key):
if key < self.key:
self.left_child.binary_tree_delete(key)
elif key > self.key:
self.right_child.binary_tree_delete(key)
else: # delete the key here
if self.left_child and self.right_child: # if both children are present
successor = self.right_child.find_min()
self.key = successor.key
successor.binary_tree_delete(successor.key)
elif self.left_child: # if the node has only a *left* child
self.replace_node_in_parent(self.left_child)
elif self.right_child: # if the node has only a *right* child
self.replace_node_in_parent(self.right_child)
else: # this node has no children
self.replace_node_in_parent(None)
Main Method:
public static void main(String[] arg){
MinHeapmh=new MinHeap();
mh.insert(2);
mh.insert(4);
mh.insert(1);
mh.insert(10);
mh.insert(3);
mh.insert(6);
mh.insert(15);
mh.insert(12);
mh.insert(16);
mh.insert(5);
while(!mh.isEmpty()){
System.out.println(mh.remove());
}
public class MinHeap >
{
private E[] heap;
private int size = 0;
private static final int DEFAULT_CAPACITY = 8;
public MinHeap(int capacity)
{
heap = (E[]) new Comparable[capacity];
}
public MinHeap()
{
this(DEFAULT_CAPACITY);
}
public int size()
{
return _____;
}
public boolean isEmpty()
{
return size() == _____;
}
private void expand()
{
E[] newHeap = (E[]) new Comparable[heap.length * 2];
for (int i = 0; i < size(); i++)
{
newHeap[i] = heap[i];
}
heap = newHeap;
}
private void swapElements(int p1, int p2)
{
E temp = heap[p1];
heap[p1] = heap[p2];
heap[p2] = temp;
}
private int getParentIndex(int childIndex)
{
// if odd, child is a left node
if (childIndex % 2 != 0) {
return childIndex / 2;
}
// if even, child is a right node
else
{
return childIndex / 2 - 1;
}
}
public void insert(E element)
{
int position = size();
if (position == heap.length)
{
expand();
}
size++;
heap[position] = element;
int parent = getParentIndex(position);
while (position > 0 && heap[position].compareTo(heap[parent]) < 0)
{
// if parent is greater, swap parent and node
swapElements(________, position);
// update position of the new element and find next parent up
position = getParentIndex(position);
parent = getParentIndex(________);
}
}
public E remove()
{
if (isEmpty())
{
return null;
}
// take out root and place last node at root position
E min = heap[0];
heap[____] = heap[size() - 1];
heap[size() - 1] = null; // optional
size--;
// position of new root and its smaller child
int position = 0;
int smallerChild = smallerChildIndex(position);
// while there is a smaller child, swap parent and child
while (__________ != position) {
swapElements(position, smallerChild);
// update position of node and get new smaller child
position = smallerChild;
smallerChild = smallerChildIndex(_______);
}
return min;
}
}
Method for finding the smaller child element:
private int smallerChildIndex(int getParentIndex) {
int smaller = getParentIndex;
// get left child index
int leftChild = 2 * getParentIndex + 1;
// if the left child index is in bounds of the heap...
if (leftChild < size() - 1) {
// set smaller to left if left is smaller than parent
smaller = heap[leftChild].compareTo(heap[smaller]) < 0
? leftChild : smaller;
// get right child index
int rightChild = 2 * getParentIndex + 2;
// if the right child index is in bounds of the heap...
if (rightChild < size() - 1) {
// set smaller to right if right is smaller than parent
smaller = heap[rightChild].compareTo(heap[smaller]) < 0
? rightChild : smaller;
}
}
return smaller;
}
Input: 7, 3, 6, 2, 9, 1, 10,
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.