Java-data structures P4 Statisticians often are interested in the median value i
ID: 3831885 • Letter: J
Question
Java-data structures
P4
Statisticians often are interested in the median value in a collection of data. In a collection, about the same number of values are greater than the median value as are less than the median value. When the data is sorted, the median value occurs at the midpoint of the collection. But when the data is not sorted, the median is not as easy to find.
A problem more general than finding the median is to find the k th smallest value in a collection of n values, where 0 < k < n. To find the median, k would be [n/2]—that is, the smallest integer greater than or equal to n/2. For example, the median value of 11 items is the 6th smallest one.
Design an algorithm that uses a maxheap to find the k th smallest value in a collection of n values. Implement your algorithm as a method
public static Integer getKthSmallest(ArrayList<Integer> aList, int k)
in the file MaxHeap.java
MaxHeap.java
import java.util.Arrays;
public class MaxHeap < T extends Comparable < ? super T >> implements MaxHeapInterface
{
private T [] heap; // array of heap entries
private int lastIndex; // index of last entry
private static final int DEFAULT_INITIAL_CAPACITY = 25;
public MaxHeap () {
this (DEFAULT_INITIAL_CAPACITY); // call next constructor
} // end default constructor
public MaxHeap (int initialCapacity) {
// the cast is safe because the new array contains all null entries
@ SuppressWarnings ("unchecked")
T [] tempHeap = (T []) new Comparable [initialCapacity + 1];
heap = tempHeap;
lastIndex = 0;
} // end constructor
public void add (T newEntry) {
lastIndex++;
ensureCapacity ();
int newIndex = lastIndex;
int parentIndex = newIndex / 2;
while ((parentIndex > 0) && newEntry.compareTo (heap [parentIndex]) > 0) {
heap [newIndex] = heap [parentIndex];
newIndex = parentIndex;
parentIndex = newIndex / 2;
} // end while
heap [newIndex] = newEntry;
} // end add
public T removeMax () {
T root = null;
if (!isEmpty ()) {
root = heap [1]; // return value
heap [1] = heap [lastIndex]; // form a semiheap
lastIndex--; // decrease size
reheap (1); // transform to a heap
} // end if
return root;
} // end removeMax
public T getMax () {
T root = null;
if (!isEmpty ())
root = heap [1];
return root;
} // end getMax
public boolean isEmpty () {
return lastIndex < 1;
} // end isEmpty
public int getSize () {
return lastIndex;
} // end getSize
public void clear () {
for (; lastIndex > -1 ; lastIndex--)
heap [lastIndex] = null;
lastIndex = 0;
} // end clear
// Private methods
private void reheap (int rootIndex) {
boolean done = false;
T orphan = heap [rootIndex];
int leftChildIndex = 2 * rootIndex;
while (!done && (leftChildIndex <= lastIndex))
{
int largerChildIndex = leftChildIndex; // assume larger
int rightChildIndex = leftChildIndex + 1;
if ((rightChildIndex <= lastIndex) &&
heap [rightChildIndex].compareTo (heap [largerChildIndex]) > 0)
{
largerChildIndex = rightChildIndex;
} // end if
if (orphan.compareTo (heap [largerChildIndex]) < 0)
{
heap [rootIndex] = heap [largerChildIndex];
rootIndex = largerChildIndex;
leftChildIndex = 2 * rootIndex;
}
else
done = true;
} // end while
heap [rootIndex] = orphan;
} // end reheap
} // end MaxHeap
MaxHeapInterface.java
public interface MaxHeapInterface<T extends Comparable<? super T>> {
public void add (T newEntry);
public T removeMax ();
public T getMax ();
public boolean isEmpty ();
public int getSize ();
public void clear ();
}
Explanation / Answer
Please find my code:
1) Build a Max-Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the k’th element (arr[k] to arr[n-1]), compare it with root of MH.
……a) If the element is less than the root then make it root and call heapify for MH
……b) Else ignore it.
// The step 2 is O((n-k)*logk)
3) Finally, root of the max heap is the kth smallest element.
import java.util.ArrayList;
import java.util.Arrays;
public class MaxHeap < T extends Comparable < ? super T >> implements MaxHeapInterface
{
private T [] heap; // array of heap entries
private int lastIndex; // index of last entry
private static final int DEFAULT_INITIAL_CAPACITY = 25;
public MaxHeap () {
this (DEFAULT_INITIAL_CAPACITY); // call next constructor
} // end default constructor
public MaxHeap (int initialCapacity) {
// the cast is safe because the new array contains all null entries
@ SuppressWarnings ("unchecked")
T [] tempHeap = (T []) new Comparable [initialCapacity + 1];
heap = tempHeap;
lastIndex = 0;
} // end constructor
public void add(T newEntry) {
lastIndex++;
ensureCapacity ();
int newIndex = lastIndex;
int parentIndex = newIndex / 2;
while ((parentIndex > 0) && newEntry.compareTo (heap [parentIndex]) > 0) {
heap [newIndex] = heap [parentIndex];
newIndex = parentIndex;
parentIndex = newIndex / 2;
} // end while
heap [newIndex] = newEntry;
} // end add
public T removeMax () {
T root = null;
if (!isEmpty ()) {
root = heap [1]; // return value
heap [1] = heap [lastIndex]; // form a semiheap
lastIndex--; // decrease size
reheap (1); // transform to a heap
} // end if
return root;
} // end removeMax
public T getMax () {
T root = null;
if (!isEmpty ())
root = heap [1];
return root;
} // end getMax
public boolean isEmpty () {
return lastIndex < 1;
} // end isEmpty
public int getSize () {
return lastIndex;
} // end getSize
public void clear () {
for (; lastIndex > -1 ; lastIndex--)
heap [lastIndex] = null;
lastIndex = 0;
} // end clear
// Private methods
private void reheap (int rootIndex) {
boolean done = false;
T orphan = heap [rootIndex];
int leftChildIndex = 2 * rootIndex;
while (!done && (leftChildIndex <= lastIndex))
{
int largerChildIndex = leftChildIndex; // assume larger
int rightChildIndex = leftChildIndex + 1;
if ((rightChildIndex <= lastIndex) &&
heap [rightChildIndex].compareTo (heap [largerChildIndex]) > 0)
{
largerChildIndex = rightChildIndex;
} // end if
if (orphan.compareTo (heap [largerChildIndex]) < 0)
{
heap [rootIndex] = heap [largerChildIndex];
rootIndex = largerChildIndex;
leftChildIndex = 2 * rootIndex;
}
else
done = true;
} // end while
heap [rootIndex] = orphan;
} // end reheap
public static Integer getKthSmallest(ArrayList<Integer> aList, int k){
MaxHeap<Integer> maxHeap = new MaxHeap<>(aList.size());
for(int i=0; i<k; i++)
maxHeap.add(aList.get(i));
for(int i=k; i<aList.size(); i++){
if(maxHeap.getMax() > aList.get(i)){
maxHeap.removeMax();
maxHeap.add(aList.get(i));
}
}
// root contains kth smallest
return maxHeap.getMax();
}
}
// end MaxHeap
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.