Algorithms In Java

Tournament Tree or Winner Tree :  Is a form of min(max) heap which is a complete binary tree. every external node represents a player and internal node represents a winner. Winner: select the best player among N palyers , (N -1) players to be eliminated. we need minimum of (N-1) games (comparisons). Second best player: we can pick second best player in (N + log2(n-2)) comparisons.   The above tree contains 4 leaf nodes that represent players and have 3 levels 0, 1 and 2. Initially 2 games are conducted at level 2, one between 5 and 3 and another one between 7 and 8. In the next move, one more game is conducted between 5 and 8 to conclude the final winner. Overall we need 3 comparisons. For second best player we need to trace the candidates participated with final winner, that leads to 7 as second best. Uses: Tree selection sort using tournament tree.  

 A Binary Heap is either Min Heap or Max Heap. Min Binary Heap: the key at root must be minimum among all keys present in Binary Heap. the same property must be recursively true for all nodes in Binary Tree. Min Binary Heap: The key at root must be maximum among all keys present in Binary Heap. the same property must be recursively true for all nodes in Binary Tree. Binamial Heap: Binamial Heap  is a Extention of Binary Heap that provides faster union or merge operations together with other operations provided by Binary Heap. Is a collection of tinomial trees. Binamial Tree Tree: A binomial Tree of order 0 has 1 node. A binomial Tree oder k can be constructed by taking two binomial trees of order k-1, and making one as leftmost child of other.  Binomial Heap: Is a set of Binomial Tree where each Binomial Tree follows Min Heap Property. and there can be at-most one Binomial Tree of any degree. Fibonacci Heap:  In terms of Time Com...

package com.nrs.ds.basic.queue.heap.sort; public class HeapSortImpl { static int total; static void swap(Comparable[] arr, int a , int b){ Comparable temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } static void heapify(Comparable[] arr , int i){ int left = i * 2; //2k int right = i * 2 + 1; // 2k+1 int grt = i; if(left <= total && arr[left].compareTo(arr[grt]) >= 0) grt = left; if(right <= total && arr[right].compareTo(arr[grt]) >= 0) grt = right; if(grt != i){ swap(arr, i , grt); heapify(arr, grt); } } static void sort(Comparable[] arr){ total = arr.length -1; for(int i=total/2; i >=0; i--){ heapify(arr, i); } for(int i=total; i >...

Node.java package com.nrs.ds.basic.queue.heap; public class Node { public int iData; public Node(int key){ iData = key; } } HeapImpl.java package com.nrs.ds.basic.queue.heap; public class HeapImpl { private Node[] heapArray; private int maxSize; private int currentSize; public HeapImpl(int mx){ maxSize = mx; currentSize= 0; heapArray= new Node[maxSize]; } public boolean isEmpty(){ return (currentSize == 0); } public boolean insert(int key){ //if array is full failure if(currentSize == maxSize){ return false; } //make a new node put it at the end, trickle it up Node newNode = new Node(key); heapArray[currentSize] = newNode; trickleUp(currentSize++); return true; } public void ...

A priority queue allows access to the smallest (or sometimes the largest) item. The important priority queue operations are inserting an item in sorted order and removing the item with the smallest key. We can use binary search to find the insertion point using a logarithmic number of compares. On average, the key to be inserted must be placed in the middle of the array—to keep the array in order, we must shift over all larger keys. Remove the largest (or smallest) item. Event-driven simulation. [customers in a line, colliding particles]  Numerical computation. [reducing roundoff error]  Data compression. [Huffman codes]  Graph searching. [Dijkstra's algorithm, Prim's algorithm]  Number theory. [sum of powers]  Artificial intelligence. [A* search]  Statistics. [maintain largest M values in a sequence]  Operating systems. [load balancing, interrupt handling]  Discrete optimization. [bin packing, scheduling]  Spam filtering...

1. Node.java package com.nrs.ds.basic.ll.ex; public class Node { char data; Node next; Node (char d){ data = d; next = null; } } 2.  LinkedListPalindromImpl.java package com.nrs.ds.basic.ll.ex; public class LinkedListPalindromImpl { Node head; Node slow_ptr, fast_ptr, second_half; boolean isPalindrome(Node head){ slow_ptr = head; fast_ptr = head; Node prev_of_slow_ptr = head; Node midnode = null; boolean result = true; if( head != null && head.next != null){ while( fast_ptr != null && fast_ptr.next != null){ fast_ptr = fast_ptr.next.next; prev_of_slow_ptr = slow_ptr; slow_ptr = slow_ptr.next; } if(fast_ptr != null){ midnode = slow_ptr; ...

Binary Tree Connected 1. Node.java package com.nrs.ds.tree.ex; public class Node { String data; Node left, right, nextRight; Node(String string){ data = string; left=right=nextRight=null; } } 2.BinaryTreeConnected.java package com.nrs.ds.tree.ex; public class BinaryTreeConnected { Node root; void connect(Node p){ p.nextRight = null; connectRecur(p); } void connectRecur(Node p){ if(p == null){ return; } if(p.left != null){ p.left.nextRight = p.right; } if(p.right != null){ p.right.nextRight = (p.nextRight != null) ? p.nextRight.left:null; } connectRecur(p.left); connectRecur(p.right); } } 3. Test package com.nrs.ds.tree.ex; public class BinaryTreeConnectTest { public...

1. Node Node.java package com.nrs.ds.tree; public class Node { int value; Node left; Node right; public Node(int value, Node left, Node right){ this.value = value; this.left = left; this.right = right; } } 2. BinarySearchTreeImpl .java package com.nrs.ds.tree; public class BinarySearchTreeImpl { Node root; public BinarySearchTreeImpl(){ root = null; } public Node nodeCreate(int value){ return new Node(value, null, null); } public void add(Node start, Node newNode){ if(root == null){ root = newNode; return; } if(newNode.value > start.value){ if(start.right == null){ start.right = newNode; } add(start.right, newNode); } if(newNode....

Hashtable A hash table is based on an array. 1. Entry.java package com.nrs.ds.hash; public class Entry { int key; Object value; Entry next; public Entry(int key, Object value){ this.key = key; this.value = value; next = null; } public Entry(){ next = null; } public int getKey(){ return key; } public Object getValue(){ return value; } } 2. HashTableArrayImpl.java package com.nrs.ds.hash; public class HashTableArrayImpl<T> { Entry[] arrayHash; int size; public HashTableArrayImpl(int size){ this.size = size; arrayHash = new Entry[size]; for(int i = 0; i < size; i++){ arrayHash[i] = new Entry(); } } int getHash(int key){ ...

Queue Linked List : 1. QueueLinked package com.nrs.ds.basic; public class QueueLinkedListImpl<T> { NodeD Rear; NodeD Front; public QueueLinkedListImpl(){ Rear = null; Front = null; } public void queue(Object value){ NodeD newNode = new NodeD(value, null ,null); if(Rear == null){ Rear = newNode; Front = newNode; }else{ newNode.next = null; newNode.previous = Rear; Rear.next = newNode; } } public T deQueue(){ if(Rear==null || Front==null){ System.out.println("Queue is empty"); return null; } T value =(T)Front.value; Front = Front.next; if(Front != null){ Front.previous = null;} return value; } } 2.T...

Queue Dynamic Array 1.  QueueDynamicArrayImpl.java package com.nrs.ds.basic; import java.util.Arrays; public class QueueDynamicArrayImpl<T> { Object[] ArrayQueue; int Rear; int Front; int size; public QueueDynamicArrayImpl(int size){ this.size = size; ArrayQueue = new Object[this.size]; Front = -1; Rear = -1; } /*never full */ public Boolean isEmpty(){ return (Rear == -1 || Front > Rear); } public void queue(Object newItem){ ensureCapacity(Rear +2 ); Rear = Rear +1; ArrayQueue[Rear] = newItem; if(Front == -1){ Front = 0; } } public T deQueue(){ if(isEmpty()){ System.out.println("D Queue is Empty"); return null; } T ObejctOut = (T) ArrayQueue[Front]; Front = Front + 1; re...

Queue Array 1. QueueArrayImpl.java package com.nrs.ds.basic; public class QueueArrayImpl<T> { Object[] ArrayQueue; int Rear; int Front; int size; public QueueArrayImpl(int size){ this.size = size; ArrayQueue = new Object[this.size]; Front = -1; Rear = -1; } public Boolean isFull(){ return (Rear == size-1); } public Boolean isEmpty(){ return (Rear == -1 || Front > Rear); } public void queue(Object newItem){ if(isFull()){ System.out.println("Queue is full"); return; } Rear = Rear +1; ArrayQueue[Rear] = newItem; if(Front == -1){ Front = 0; } } public T deQueue(){ if(isEmpty()){ System.out.println("Queue is Empty"); return null; } T Obe...

Stack Linked List 1. StackLinkedListImpl.java package com.nrs.ds.basic; public class StackLinkedListImpl<T> { NodeLL top; public StackLinkedListImpl(){ top = null; } public void push(Object value){ NodeLL newNode= new NodeLL(value, null); if(top == null){ top = newNode; }else{ newNode.next = top; top = newNode; } } public T pop(){ if(top == null){ System.out.println("Stack is empty"); return null; } T value = (T) top.value; top = top.next; return value; } } 2. Test package com.nrs.ds.basic; public class StackLLTest { public static void main(String[] args) { StackLinkedListImpl<String> sl = new StackLinkedListImpl<String>(); sl.pop()...

Stack Array implementaion 1. StackArrayImpl.java package com.nrs.ds.basic; public class StackArrayImpl<T> { Object[] ArrayStack; int size; int top; public StackArrayImpl(int size){ this.size = size; ArrayStack = new Object[this.size]; top =-1; } public Boolean isFull(){ return (top == size-1); } public Boolean isEmpty(){ return top == -1; } public void push(Object newItem){ if(isFull()){ System.out.println("Stack is full"); return; } top = top + 1; ArrayStack[top] = newItem; } public T pop(){ if(isEmpty()){ System.out.println("Stack is Empty"); return null; } T item = (T)ArrayStack[top]; top = top - 1; ret...

Dynamic Array 1. DynamicArrayImpl.java package com.nrs.ds.basic; import java.util.Arrays; public class DynamicArrayImpl<T> { Object[] data; int size; public DynamicArrayImpl(){ size = 0; data = new Object[1]; } public int getSize(){ return data.length; } public T get(int index){ return (T)data[index]; } public void put(Object element){ ensureCapacity(size+1); data[size++] = element; } public void ensureCapacity(int minCapacity){ int oldCapacity = getSize(); if(minCapacity > oldCapacity){ int newCapacity = oldCapacity * 2; if(newCapacity < minCapacity){ newCapacity = minCapacity; } data = Arrays.copyOf(data, newCapacity); } } } 2. Test package com.n...

One Dimensional Array; 1.  OneDimArray.java package com.nrs.ds.basic; public class OneDimArray { public static void main(String[] args) { int[] numbers = new int[5]; numbers[0] = 20; numbers[1] = 10; numbers[2] = 12; numbers[3] = 4; numbers[4] = 4; for (int i = 0; i < numbers.length; i++) { System.out.println(numbers[i]); } } } Output:

Double Linked List 1. NodeD.java package com.nrs.ds.basic; public class NodeD { Object value; NodeD next; NodeD previous; public NodeD(Object value, NodeD next, NodeD previous){ this.value = value; this.next = next; this.previous = previous; } } 2. Double Linked List Implementation DoubleLinkedListI.java package com.nrs.ds.basic; public class DoubleLinkedListI<T> { NodeD head; public DoubleLinkedListI(){ head = null; } public void add(Object value){ NodeD newNode = new NodeD(value, null,null); if(head == null){ head = newNode; }else{ newNode.next = head; head.previous = newNode; head = newNode; } } public void delete(){ head = head.next; head.previous = null; } ...

single linked list: 1. Node class NodeLL.java package com.nrs.ds.basic; public class NodeLL { Object value; NodeLL next; public NodeLL(Object value,NodeLL next){ this.value=value; this.next = next; } } 2. LinkedList implementation LinkedListImpl.java package com.nrs.ds.basic; public class LinkedListImpl<T> { NodeLL head; public LinkedListImpl(){ head = null; } public void add(Object value){ NodeLL newNode= new NodeLL(value,null); if(head == null){ head=newNode; }else{ newNode.next = head; head = newNode; } } public void delete(){ head = head.next; } public void display(){ NodeLL n=head; while(n != null){ System.out.println((T)n.value); n = n.next; } } ...

A simple program that represents the two dimensional array package com.nrs.ds.basic; public class TwoDimensionalArray { public static void main(String[] args) { int[][] data = new int[3][3]; data[0][0]=1; data[0][1]=2; data[0][2]=3; data[1][0]=4; data[1][1]=5; data[1][2]=6; data[2][0]=7; data[2][1]=0; data[2][2]=0; for(int i=0;i<3;i++) { for(int j=0;j<3;j++){ System.out.println(data[i][j]+" \t"); } System.out.println("\n"); } } } Output: If we want write any conditions like for(int i=0;i<3;i++) { for(int j=0;j<3;j++){ if(i==j) System.out.println(data[i][j]+" \t"); } System.out.println("\n"); } Output: ...

Simple program that creates an array of students. package com.nrs.ds.basic; public class StudentArray { String name; int age; public StudentArray(String name, int age) { this.name = name; this.age = age; } public static void main(String[] args) { StudentArray[] students= new StudentArray[5]; students[0] = new StudentArray("Naresh",24); students[1] = new StudentArray("Pratap",22); students[2] = new StudentArray("Pavan",23); students[3] = new StudentArray("Imran",24); students[4] = new StudentArray("Tirumal",25); for(StudentArray student : students){ System.out.println("Student Name:"+student.name+" ,"+"Student Age :"+student.age); } } } Output: