Java program to create a Binary Heap and Perform various operation

A binary heap (min-heap) is a complete binary tree with elements from a partially ordered set, such that the element at every node is less than (or equal to) the the element at it's left and right child. This Binary Heap is a min-heap implemented with one-based array (root is element 1; children of element n are elements 2n and 2n+1) for simplicity. Complexity: Space O(n), findMin O(1), insert O(logn), deleteMin O(logn), buildHeap O(n); class BinaryHeap { private int nodes[]; private int size; private int capacity; public BinaryHeap(int...

[ Read More ]

Create an Adjacency matrix Graph and perform Add and Remove operation

import java.util.ArrayList; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Stack; /** * Implementation of a directed unweighted Graph using Adjacency Matrix * * Complexity: addEdge, removeEdge, hasEdge O(1) / outEdges, inEdges O(n) / * Space O(n^2) */ public class AdjMatrixGraph { int size; private boolean[][] matrix; public static final byte WHITE = 1; public static final byte GREY = 2; public AdjMatrixGraph(int size) { this.size = size; this.matrix =...

[ Read More ]

To Sort an Interger Array using Shell Sort

To Sort an Interger Array using Shell Sort class ShellSort { public static int[] shellSort(int[] array) { int N = array.length; // determine the initial h value int h = 1; while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ... while (h >= 1) { // h-sort the array for (int i = h; i < array.length; i++) { // do insertion sort for h-sized array for (int j = i; j >= h && array[j] < array[j - h]; j -= h) swap(array, j, j - h); } ...

[ Read More ]

Sort an Integer array with Bucket Sort

Here is a java program to Sort an Integer array with Bucket Sort class BucketSort { public int[] bucketSort(int[] array) { // create an array the size of the largest value + 1 int[] bucket = new int[100]; // for every value in array, increment its corresponding bucket for (int i = 0; i < array.length; i++) bucket[array[i]]++; int outPos = 0; for (int i = 0; i < bucket.length; i++) { if (bucket[i] > 0) array[outPos++] = i; } ...

[ Read More ]

Merge-Sort Algorithm implementation in JAVA

Merge-Sort Function void MergeSort(int low, int high) // a[low : high] is a global array to be sorted. // Small(P) is true if there is only one element to // sort. In this case the list is already sorted. { if (low < high) { // If there are more than one element // Divide P into subproblems. // Find where to split the set. int mid = (low + high)/2; // Solve the subproblems. MergeSort(low, mid); MergeSort(mid + 1, high); //...

[ Read More ]

Implementation of a basic generic tree, with labels of type T - Data Structure

// This implements a basic generic tree, with labels of type T, // pointer to the parent node, and a singly linked list of children nodes. class Tree<T> { private T label; private Tree<T> parent; private Tree<T> nextSibling; // next node on the list of parents's // children private Tree<T> firstChild; // first in the linked list of children // Getters and setters public T getLabel() { return label; } public void setLabel(T...

[ Read More ]

Stack implemented as array - Data Structure

// Stack implemented as array public class ArrayStack<T> { private T[] stack; private int numElements = 0; // points to slot after top element public ArrayStack(T[] s) { stack = s; } public boolean emptyStack() { return numElements == 0; } public T top() { return stack[numElements-1]; } public void push(T x) { stack[numElements] = x; numElements++; } public T pop() { numElements--; return stack[numElements]; } ...

[ Read More ]