Compute the asymptotic run time and space complexity for all the methods in the
ID: 3699196 • Letter: C
Question
Compute the asymptotic run time and space complexity for all the methods in the following code:
public class MaxHeap {
// Instance variables
private Integer[] heap;
private int capacity; // Amount of memory allocated
private int size; // Num of items stored
/**
* Parameterized constructor
*
* @param initialCapacity
* - initial amount of memory allocated
*/
public MaxHeap(int initialCapacity) {
this.capacity = initialCapacity;
this.size = 0;
this.heap = new Integer[this.capacity];
}
/**
* Parameterized constructor
*
* @param someArray
* - Array containing some integers
*/
public MaxHeap(Integer[] someArray) {
this(someArray.length);
// Insert all elements in someArray into heap
for (Integer n : someArray)
insert(n);
}
/**
* Inserts value n in this max heap. Duplicates are allowed. If there is no
* room for insertion in the current array storing the items, then an array
* of double size has to be allocated and all items are copied into the new
* array after which insertion is performed.
*
* @param n
* - item to be inserted
*/
public void insert(int n) {
// Check if there is room for insertion
if (this.capacity == this.size) {
// Double the capacity
this.capacity *= 2;
// Create new array with double size
Integer[] newArray = new Integer[this.capacity];
// Copy elements from heap array to newArray
for (int i = 0; i < this.size; i++)
newArray[i] = this.heap[i];
// Point heap to newArray
this.heap = newArray;
}
// Insert n into heap
this.heap[this.size] = new Integer(n);
// Increment size
this.size += 1;
// Build max heap
buildHeap();
}
/**
* Build heap
*/
private void buildHeap() {
for (int i = (this.size - 1) / 2; i >= 0; i--)
buildMaxHeap(i);
}
/**
* Builds max heap
*/
private void buildMaxHeap(int i) {
int left = (2 * i) + 1;
int right = (2 * i) + 2;
int max = i;
int len = this.size - 1;
// Check if element at left is greater than element at max
if ((left <= len) && (this.heap[left] > this.heap[max]))
max = left;
// Check if element at right is greater than element at max
if ((right <= len) && (this.heap[right] > this.heap[max]))
max = right;
if (max != i) {
// Swap element at i with element at max
Integer temp = new Integer(this.heap[i].intValue());
this.heap[i] = new Integer(this.heap[max].intValue());
this.heap[max] = new Integer(temp.intValue());
// Check the swapped position if it satisfies the max heap process
buildMaxHeap(max);
}
}
/**
* Removes the item with the largest value and returns it.
*
* @return - the item with the largest value
*/
private int deleteMax() {
Integer largestVal = null;
if (this.size > 0) {
// Get largest value
largestVal = this.heap[0];
// Move all elements one position up
for (int i = 1; i < this.size; i++)
this.heap[i - 1] = new Integer(this.heap[i].intValue());
// Decrement size
this.size -= 1;
}
// Create max heap
buildHeap();
return largestVal;
}
/**
* Returns a string representing the sequence of integer values stored in
* the heap, in order they are stored in the array
*/
public String toString() {
StringBuffer sb = new StringBuffer();
for (Integer n : heap)
sb.append(n + " ");
return sb.toString();
}
/**
* Applies heap sort algorithm to sort the input array.
*
* @param arrayToSort
* - Array to sort
*/
public static void heapsort(Integer[] arrayToSort) {
// Create MaxHeap object
MaxHeap maxHeap = new MaxHeap(arrayToSort);
// Create an array to hold the sorted
Integer[] newArray = new Integer[maxHeap.getSize()];
// Delete max element until size of maxHeap is not zero
int index = 0;
while (maxHeap.getSize() != 0)
newArray[index++] = maxHeap.deleteMax();
// Copy items from newArray to arrayToSort
for (int i = 0; i < newArray.length; i++)
arrayToSort[i] = new Integer(newArray[i].intValue());
}
/**
* @return the capacity
*/
public int getCapacity() {
return capacity;
}
/**
* @return the size
*/
public int getSize() {
return size;
}
public static void main(String[] args) {
// Create an array of integers
Integer[] arrayToSort = new Integer[] { 3, 5, 9, 6, 8, 20, 10, 12, 18, 9 };
// Display original array
System.out.print("Original array: ");
for (Integer n : arrayToSort)
System.out.print(n + " ");
// Create max heap
MaxHeap.heapsort(arrayToSort);
// Display sorted array
System.out.print(" Sorted array: ");
for (Integer n : arrayToSort)
System.out.print(n + " ");
}
}
Explanation / Answer
//Answers are in BOLD
public class MaxHeap {
// Instance variables
private Integer[] heap;
private int capacity; // Amount of memory allocated
private int size; // Num of items stored
/**
* Parameterized constructor
*
* @param initialCapacity
* - initial amount of memory allocated
*/
// Constructor to initialise the values that takes O(1) time and Space
public MaxHeap(int initialCapacity) {
this.capacity = initialCapacity;
this.size = 0;
this.heap = new Integer[this.capacity];
}
/**
* Parameterized constructor
*
* @param someArray
* - Array containing some integers
*/
public MaxHeap(Integer[] someArray) {
this(someArray.length);
// Insert all elements in someArray into heap
for (Integer n : someArray)
insert(n);
}
/**
* Inserts value n in this max heap. Duplicates are allowed. If there is no
* room for insertion in the current array storing the items, then an array
* of double size has to be allocated and all items are copied into the new
* array after which insertion is performed.
*
* @param n
* - item to be inserted
*/
// If we insert n elements Build heap takes O(n) time . Hence time and space complexituy insert Is O(n)
public void insert(int n) {
// Check if there is room for insertion
if (this.capacity == this.size) {
// Double the capacity
this.capacity *= 2;
// Create new array with double size
Integer[] newArray = new Integer[this.capacity];
// Copy elements from heap array to newArray
for (int i = 0; i < this.size; i++)
newArray[i] = this.heap[i];
// Point heap to newArray
this.heap = newArray;
}
// Insert n into heap
this.heap[this.size] = new Integer(n);
// Increment size
this.size += 1;
// Build max heap
buildHeap();
}
/**
* Build heap
*/
//Takes O(n) time and O(1) space to build heap of n elements
private void buildHeap() {
for (int i = (this.size - 1) / 2; i >= 0; i--)
buildMaxHeap(i);
}
/**
* Builds max heap
*/
//This function takes O(logn) time and O(1) space
private void buildMaxHeap(int i) {
int left = (2 * i) + 1;
int right = (2 * i) + 2;
int max = i;
int len = this.size - 1;
// Check if element at left is greater than element at max
if ((left <= len) && (this.heap[left] > this.heap[max]))
max = left;
// Check if element at right is greater than element at max
if ((right <= len) && (this.heap[right] > this.heap[max]))
max = right;
if (max != i) {
// Swap element at i with element at max
Integer temp = new Integer(this.heap[i].intValue());
this.heap[i] = new Integer(this.heap[max].intValue());
this.heap[max] = new Integer(temp.intValue());
// Check the swapped position if it satisfies the max heap process
buildMaxHeap(max);
}
}
/**
* Removes the item with the largest value and returns it.
*
* @return - the item with the largest value
*/
// This function moves all the element one up. Hence the function takes O(n) time and O(1) space
private int deleteMax() {
Integer largestVal = null;
if (this.size > 0) {
// Get largest value
largestVal = this.heap[0];
// Move all elements one position up
for (int i = 1; i < this.size; i++)
this.heap[i - 1] = new Integer(this.heap[i].intValue());
// Decrement size
this.size -= 1;
}
// Create max heap
buildHeap();
return largestVal;
}
/**
* Returns a string representing the sequence of integer values stored in
* the heap, in order they are stored in the array
*/
/// This function iterates all the element. Hence the function takes O(n) time and O(1) space
public String toString() {
StringBuffer sb = new StringBuffer();
for (Integer n : heap)
sb.append(n + " ");
return sb.toString();
}
/**
* Applies heap sort algorithm to sort the input array.
*
* @param arrayToSort
* - Array to sort
*/
//n itesma dn each delete n time, So overall time complexity is O(n2) time and O(1) space
public static void heapsort(Integer[] arrayToSort) {
// Create MaxHeap object
MaxHeap maxHeap = new MaxHeap(arrayToSort);
// Create an array to hold the sorted
Integer[] newArray = new Integer[maxHeap.getSize()];
// Delete max element until size of maxHeap is not zero
int index = 0;
while (maxHeap.getSize() != 0)
newArray[index++] = maxHeap.deleteMax();
// Copy items from newArray to arrayToSort
for (int i = 0; i < newArray.length; i++)
arrayToSort[i] = new Integer(newArray[i].intValue());
}
/**
* @return the capacity
*/
//O(1) time and space
public int getCapacity() {
return capacity;
}
/**
* @return the size
*/
//O(1) time and space
public int getSize() {
return size;
}
public static void main(String[] args) {
// Create an array of integers
Integer[] arrayToSort = new Integer[] { 3, 5, 9, 6, 8, 20, 10, 12, 18, 9 };
// Display original array
System.out.print("Original array: ");
for (Integer n : arrayToSort)
System.out.print(n + " ");
// Create max heap
MaxHeap.heapsort(arrayToSort);
// Display sorted array
System.out.print(" Sorted array: ");
for (Integer n : arrayToSort)
System.out.print(n + " ");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.