Given a (Java) LinkedList , write a function that returns the k th minimum element from the arraylist
^recursive method plz, psudocode is fine
Please find my full working code (you can treat as pseudo code also) in Java using Min Heap.
import java.util.ArrayList;
public class MinHeapArrayList
{
public static int kthMinimum(ArrayList<Integer> arr, int k)
{
int n = arr.size();
BuildMinHeap(arr, n);
int min = Integer.MIN_VALUE;
// One by one extract an element from heap
for (int i=1; i <=k; i++)
{
// Move current root to end
int temp = arr.get(0);
arr.set(0, arr.get(n-1));
arr.set(n-1, temp);
n = n-1;
min = temp;
// call max heapify on the reduced heap
MinHeapify(arr, n, 0);
}
return min;
}
static void BuildMinHeap(ArrayList<Integer> arr, int n){
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
MinHeapify(arr, n, i);
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
static void MinHeapify(ArrayList<Integer> arr, int n, int i)
{
int smallest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr.get(l) < arr.get(smallest))
smallest = l;
// If right child is larger than largest so far
if (r < n && arr.get(r) < arr.get(smallest))
smallest = r;
// If largest is not root
if (smallest != i)
{
int swap = arr.get(i);
arr.set(i, arr.get(smallest));
arr.set(smallest, swap);
// Recursively heapify the affected sub-tree
MinHeapify(arr, n, smallest);
}
}
/* A utility function to print array of size n */
public static void display(ArrayList<Integer> arr)
{
int n = arr.size();
for (int i=0; i<n; ++i)
System.out.print(arr.get(i)+" ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {15,13,9,5,12,8,7,4,0,6,2,1};
ArrayList<Integer> list = new ArrayList<>();
for(int x : arr)
list.add(x);
System.out.println("4th min: "+kthMinimum(list, 4));
}
}
/*
Sample run:
4th min: 4
*/
Please let me know in case of any issue
Given a (Java) LinkedList , write a function that returns the k th minimum element from...
Given an ArrayList , write a function that returns the k th minimum element from the arraylist. Note: 0 th minimum element is the smallest element in the ArrayList ^ plz find a recursive method, psudocode is fine
JAVA - Write a function in your Main class LinkedList<E> mergeLists(LinkedList<E> list1, LinkedList<E> list2) - given two ordered linked lists of integers, merge the two lists into a single LinkedList whose elements are in sorted order. You should create a new LinkedList and add the values from list1 and list2 into the new list in sorted order. Do not modify list1 or list 2. list1 => 1 -> 3 -> 7 -> 8, list2 => 2 -> 5 -> 7...
I need to write a method in java that returns void and takes a String element. ex :public void addelemt(String element) the method job is to add elements to an ArrayList as many times as the person wants. please, no use of a switch or do.
Solve the following LinkedList problems. You can use the LinkedList class from the previous lab. Write the following methods for the LinkedList class Problem 1: Write a method that deletes the first half of the list. Problem 2: Write a method that deletes the second half of the list. Problem 3: Write a method that deletes every other element in the list. Problem 4: Write a method that, given a second LinkedList, creates and returns a third list containing all...
Write a recursive function that returns the minimum key value in a binary search tree of distinct (positive) integers. Return -1 in case the tree is empty. (b) Write a recursive function that returns the predecessor of the key value k in a binary search tree of distinct (positive) integers. This is the key value that precedes k in an inorder traversal of the tree. If k does not exist, or if k has no predecessor, your function should return...
JAVA Write a recursive method that writes a given array backward. Consider the last element of the array first.
Write a program in Java to implement a recursive boolean function that returns True if the given array contents remain the same when the array is reversed. Otherwise function must return False.
JAVA PROGRAMMING PLEASE This lab has three parts: Create an ArrayList class. Create a LinkedList class. Print out the results after testing each of the methods in both of the classes and solving a simple problem with them. Task 1 – ArrayList Class Create an ArrayList class. This is a class that uses an internal array, but manipulates the array so that the array can be dynamically changed. This class should contain a default and overloaded constructor, where the default...
"Java question" Implement a generic method that returns the minimum element in an array. public static<EextendsComparable<E>> E min(E[ ] list)
JAVA Write Java code for extending the LinkedList class of java.util.* to ExtLinkedList that would include the following method: public ExtLinkedList firstHalfList() which returns the first half of the list. In other words, if you have a ExtLinkedList of size 5, for example, the method firstHalfList should return the list with the first two nodes. If it is a list of size 6, it should return the list with the first three nodes. The original list should not be modified....