Question

a) Create a class MinHeap implementation using an Array. Find the kth smallest value in a collection of n values, where 0 < k < n. Write a program that uses a minheap method to find the kth smallest value in a collection of n values. Use the MinHeap class defined in part a.

public final class MinHeap<T extends Comparable<? super T>>

             implements MinHeapInterface<T>

{

   private T[] heap;      // Array of heap entries; ignore heap[0]

   private int lastIndex; // Index of last entry and number of entries

   private boolean integrityOK = false;

private static final int DEFAULT_CAPACITY = 25;

private static final int MAX_CAPACITY = 10000;

...

}

/** An interface for the ADT minheap. */

public interface MinHeapInterface<T extends Comparable<? super T>>

{ // See Segment 24.33 for a commented version.

   public void add(T newEntry);

   public T removeMin();

   public T getMin();

   public boolean isEmpty();

   public int getSize();

   public void clear();

} // end MaxHeapInterface

Answer 1

import java.util.Arrays;

interface MinHeapInterface<T extends Comparable<? super T>>
{
    /** Adds a new entry to this heap.
    @param newEntry An object to be added. */
    public void add(T newEntry);
    
    /** Removes and returns the smallest item in this heap.
    @return Either the smallest object in the heap or,
    if the heap is empty before the operation, null. */
    public T removeMin();
    
    /** Retrieves the smallest item in this heap.
    @return Either the smallest object in the heap or,
    if the heap is empty, null. */
    public T getMin();
    
    /** Detects whether this heap is empty.
    @return True if the heap is empty, or false otherwise. */
    public boolean isEmpty();
    
    /** Gets the size of this heap.
    @return The number of entries currently in the heap. */
    public int getSize();
    
    /** Removes all entries from this heap. */
    public void clear();
} // end MinHeapInterface


public class MinHeap<K extends Comparable<K>> implements MinHeapInterface<K>{
    private static final int MAX_SIZE = 10;
    protected K[] array;
    protected int currentSize;

    /**
     * Constructs a new BinaryHeap.
     */
    @SuppressWarnings("unchecked")
    public MinHeap () {
        // In Java, we can not create a generics array, so we need to typecast it
        array = (K[])new Comparable[MAX_SIZE];  
        currentSize = 0;
    }

    /**
     * Constructs a new BinaryHeap.
     */
    @SuppressWarnings("unchecked")
    public MinHeap (K elements[]) {
        // In Java, we can not create a generics array, so we need to typecast it
        array = (K[])new Comparable[MAX_SIZE];  
        currentSize = 0;
        
        for(K e: elements) {
            add(e);
        }
    }

    @SuppressWarnings("unchecked")
    public void clear() {
        array = (K[])new Comparable[MAX_SIZE];  
        currentSize = 0;
    }
    
    /**
     * Add this element to the heap
     */
    public void add(K value) {
        // check if array need to be resized
        if (currentSize >= array.length - 1) {
            array = this.resize();
        }
        
        // place element into heap at the last position
        // and then we will check if minHeapify property is valid or not
        currentSize++;
        
        int index = currentSize;
        array[index] = value;
        
        heapifyupwards();
    }
    
    
    /**
     * Returns true if the heap has no elements; false otherwise.
     */
    public boolean isEmpty() {
        return currentSize == 0;
    }
    
    /**
     * Remove the min element from the heap and return it
     */
    public K removeMin() {
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }
        // what do want return?
        K result = array[1];
        
        // move the last leaf node at root and root to the last leaf
        // then we will remove the last node and from new root
        // we will heapifyDownwards
        array[1] = array[currentSize];
        array[currentSize] = null;
        currentSize--;
        
        heapifyDownwards(1);
        
        return result;
    }
    
    public int getSize() {
        return currentSize;
    }
    
    public K getMin() {
        if(isEmpty()) {
            return null;
        }
        return array[1];
    }
    
    boolean remove(K key) {
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }
        int index = -1;
        for(int i=0; i<currentSize; i++) {
            if(array[i].equals(key)) {
                index = i;
                break;
            }
        }
        
        if(index == -1) {
            return false;
        } else {
            array[0] = 
            array[index] = array[currentSize];
            array[currentSize] = null;
            currentSize--;
            heapifyDownwards(index);
            return true;
        }
        
    }
    
    /**
     * Performs the "bubble down" operation to place the element that is at the 
     * root of the heap in its correct place so that the heap maintains the 
     * min-heap order property.
     */
    protected void heapifyDownwards(int index) {
        
        // start from root, go to smaller of left and right node
        while (hasLeftChild(index)) {
            // which of my children is smaller?
            int smallerChild = leftIndex(index);
            if (hasRightChild(index)
                && array[leftIndex(index)].compareTo(array[rightIndex(index)]) > 0) {
                smallerChild = rightIndex(index);
            }
            
            // check if required to swap to maintain the heapify behavior 
            if (array[index].compareTo(array[smallerChild]) > 0) {
                swap(index, smallerChild);
            } else {
                break;
            }
            
            // go in into the tree where small child is present.
            index = smallerChild;
        }        
    }
    
    
    /**
     * This method starts from the last leaf node and recursively checks till
     * root, whether the entire tree is min-heapified or not
     */
    private void heapifyupwards() {
        int index = this.currentSize;
        
        while (hasParent(index)
                && (parent(index).compareTo(array[index]) > 0)) {
            // If parent/child are out of order; swap them
            swap(index, parentIndex(index));
            
            // in next iteration proceed with checking parent node
            // we will keep doing this till we reach root of tree
            index = parentIndex(index);
        }        
    }
    
    // this method is used to swap the values in the array at two given indices.
    private void swap(int index1, int index2) {
        K tmp = array[index1];
        array[index1] = array[index2];
        array[index2] = tmp;        
    }
        
    private boolean hasParent(int i) {
        return i > 1;
    }    
    
    private int leftIndex(int i) {
        return i * 2;
    }
        
    private int rightIndex(int i) {
        return i * 2 + 1;
    }
        
    private boolean hasLeftChild(int i) {
        return leftIndex(i) <= currentSize;
    }    
    
    private boolean hasRightChild(int i) {
        return rightIndex(i) <= currentSize;
    }
        
    private K parent(int i) {
        return array[parentIndex(i)];
    }    
    
    private int parentIndex(int i) {
        return i / 2;
    }
    
    private K[] resize() {
        // this method basically creates another array, which is of double capacity
        // it also restores the elements which are already present.
        return Arrays.copyOf(array, array.length * 2);
    }
    
    
    public static void main(String args[]) {
        MinHeap<Integer> data = new MinHeap<>();
        
        for(int i=0; i<100; i++) {
            data.add((int) (Math.random() * 1000));
        }
        
        int count = 0;
        int k = 10;
        int result = 0;
        while(count < k) {
            result = data.removeMin();
            count++;
        }
        System.out.println(k + "th element: " + result);
    }
}