Use JAVA to create the class MaxHeap as specified below to support the operation
ID: 3890673 • Letter: U
Question
Use JAVA to create the class MaxHeap as specified below to support the operations of max heaps, heapsort, and priority queues. Use the exact class and method names given below and use the default package.
public class MaxHeap {
//reference to the array
public int[] a;
//heapsize may be different from a.length
public int heapSize;
//construct a MaxHeap object
//reference the user supplied array
public MaxHeap(int [] a)
public void heapify(int i)
public void buildHeap()
//heapsort on a
public void sort()
//priority queue operations
public int maximum()
public int extractMax()
public void increaseKey(int i, int key)
public void insert (int key)
}
Explanation / Answer
Please find my implementation.
Please let me know in case of any issue.
public class MaxHeap {
//reference to the array
public int[] a;
//heapsize may be different from a.length
public int heapSize;
int parent(int i) { return (i-1)/2; }
// to get index of left child of node at index i
int left(int i) { return (2*i + 1); }
// to get index of right child of node at index i
int right(int i) { return (2*i + 2); }
//construct a MaxHeap object
//reference the user supplied array
public MaxHeap(int [] a) {
for(int i=0; i<a.length; i++)
this.a[i] = a[i];
heapSize = a.length;
}
public void heapify(int i) {
int l = left(i);
int r = right(i);
int largest = i;
if (l < heapSize && a[l] > a[i])
largest = l;
if (r < heapSize && a[r] > a[largest])
largest = r;
if (largest != i)
{
int t = a[i];
a[i] = a[largest];
a[largest] = t;
heapify(largest);
}
}
public void buildHeap() {
// Build heap (rearrange array)
for (int i = a.length / 2 - 1; i >= 0; i--)
heapify(i);
}
//heapsort on a
public void sort() {
int n = a.length;
buildHeap();
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = a[0];
a[0] = a[i];
a[i] = temp;
// call max heapify on the reduced heap
heapify(i);
}
}
//priority queue operations
public int maximum() {
if (heapSize <= 0)
return Integer.MIN_VALUE;
else
return a[0];
}
public int extractMax() {
if (heapSize <= 0)
return Integer.MIN_VALUE;
if (heapSize == 1)
{
heapSize--;
return a[0];
}
// Store the minimum value, and remove it from heap
int root = a[0];
a[0] = a[heapSize-1];
heapSize--;
heapify(0);
return root;
}
public void increaseKey(int i, int key) {
a[i] = key;
while (i != 0 && a[parent(i)] < a[i])
{
int t = a[i];
a[i] = a[parent(i)];
a[parent(i)] = t;
i = parent(i);
}
}
public void insert (int key) {
if (heapSize == a.length)
{
System.out.println(" Overflow: Could not insertKey ");
return;
}
// First insert the new key at the end
heapSize++;
int i = heapSize - 1;
a[i] = key;
// Fix the max heap property if it is violated
while (i != 0 && a[parent(i)] < a[i])
{
// swapping
int t = a[i];
a[i] = a[parent(i)];
a[parent(i)] = t;
i = parent(i);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.