Algorithms In Java

 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...