Data Structure and Algorithm

Complied by Linh Truong | Incomplete and will be updated

 

 

1 Data Structure................................................................................................................................. 1

1.1 Hash Table................................................................................................................................ 3

1.2 Dynamic Array.......................................................................................................................... 7

1.3 Linked List............................................................................................................................... 11

1.4 Stacks..................................................................................................................................... 15

1.5 Queues................................................................................................................................... 15

1.6 Set.......................................................................................................................................... 15

1.7 TreeSet................................................................................................................................... 18

1.8 Binary Search Tree (BST).......................................................................................................... 20

1.9 Heap (Max Heap/Min Heap).................................................................................................... 25

1.10 Graph................................................................................................................................... 35

2 Algorithms..................................................................................................................................... 46

2.1 Sorting.................................................................................................................................... 48

2.2 Searching................................................................................................................................ 48

2.3 Tree Traversals........................................................................................................................ 48

2.4 Breadth-First Search................................................................................................................ 55

2.5 Depth-First Search................................................................................................................... 59

2.6 Binary Search.......................................................................................................................... 64

3 Concepts....................................................................................................................................... 66

3.1 Bit Manipulation..................................................................................................................... 66

3.2 Memory (Stack VS. Heap)........................................................................................................ 66

3.3 Recursion................................................................................................................................ 66

3.4 Dynamic Programming............................................................................................................ 66

3.5 Big 0 Time & Space.................................................................................................................. 66

1 Data Structure

Java Collection Framework cheat sheet

A collection is a data structure—actually, an object—that can hold references to other objects. Usually, collections contain references to objects that are all of the same type. The collections-framework interfaces declare the operations to be performed generically on various types of collections.

Interface

Description

Collection

The root interface in the collections hierarchy from which interfaces Set, Queue and List are derived.

Set

A collection that does not contain duplicates.

List

An ordered collection that can contain duplicate elements.

Map

A collection that associates keys to values and cannot contain duplicate keys.

Queue

Typically a first-in, first-out collection that models a waiting line; other orders can be specified.

http://en.proft.me/media/java/collectionsTable.png 

1.1 Hash Table

Hashtable was part of the original java.util and is a concrete implementation of a Dictionary.

However, Java 2 re-engineered Hashtable so that it also implements the Map interface. Thus, Hashtable is now integrated into the collections framework. It is similar to HashMap, but is synchronized.

Like HashMap, Hashtable stores key/value pairs in a hash table. When using a Hashtable, you specify an object that is used as a key, and the value that you want linked to that key. The key is then hashed, and the resulting hash code is used as the index at which the value is stored within the table.

Following is the list of constructors provided by the HashTable class.

Sr.No

Constructor & Description

1

Hashtable( )

This is the default constructor of the hash table it instantiates the Hashtable class.

2

Hashtable(int size)

This constructor accepts an integer parameter and creates a hash table that has an initial size specified by integer value size.

3

Hashtable(int size, float fillRatio)

This creates a hash table that has an initial size specified by size and a fill ratio specified by fillRatio. This ratio must be between 0.0 and 1.0, and it determines how full the hash table can be before it is resized upward.

4

Hashtable(Map < ? extends K, ? extends V > t)

This constructs a Hashtable with the given mappings.

Apart from the methods defined by Map interface, Hashtable defines the following methods −

Sr.No

Method & Description

1

void clear( )

Resets and empties the hash table.

2

Object clone( )

Returns a duplicate of the invoking object.

3

boolean contains(Object value)

Returns true if some value equal to the value exists within the hash table. Returns false if the value isn't found.

4

boolean containsKey(Object key)

Returns true if some key equal to the key exists within the hash table. Returns false if the key isn't found.

5

boolean containsValue(Object value)

Returns true if some value equal to the value exists within the hash table. Returns false if the value isn't found.

6

Enumeration elements( )

Returns an enumeration of the values contained in the hash table.

7

Object get(Object key)

Returns the object that contains the value associated with the key. If the key is not in the hash table, a null object is returned.

8

boolean isEmpty( )

Returns true if the hash table is empty; returns false if it contains at least one key.

9

Enumeration keys( )

Returns an enumeration of the keys contained in the hash table.

10

Object put(Object key, Object value)

Inserts a key and a value into the hash table. Returns null if the key isn't already in the hash table; returns the previous value associated with the key if the key is already in the hash table.

11

void rehash( )

Increases the size of the hash table and rehashes all of its keys.

12

Object remove(Object key)

Removes the key and its value. Returns the value associated with the key. If the key is not in the hash table, a null object is returned.

13

int size( )

Returns the number of entries in the hash table.

14

String toString( )

Returns the string equivalent of a hash table.

Example

The following program illustrates several of the methods supported by this data structure −

Live Demo

import java.util.*;

public class HashTableDemo {

 

   public static void main(String args[]) {

      // Create a hash map

      Hashtable balance = new Hashtable();

      Enumeration names;

      String str;

      double bal;

 

      balance.put("Zara", new Double(3434.34));

      balance.put("Mahnaz", new Double(123.22));

      balance.put("Ayan", new Double(1378.00));

      balance.put("Daisy", new Double(99.22));

      balance.put("Qadir", new Double(-19.08));

 

      // Show all balances in hash table.

      names = balance.keys();

     

      while(names.hasMoreElements()) {

         str = (String) names.nextElement();

         System.out.println(str + ": " + balance.get(str));

      }       

      System.out.println();

     

      // Deposit 1,000 into Zara's account

      bal = ((Double)balance.get("Zara")).doubleValue();

      balance.put("Zara", new Double(bal + 1000));

      System.out.println("Zara's new balance: " + balance.get("Zara"));

   }

}

This will produce the following result −

Output

Qadir: -19.08

Zara: 3434.34

Mahnaz: 123.22

Daisy: 99.22

Ayan: 1378.0

 

Zara's new balance: 4434.34

 

 

1.2 Dynamic Array

The ArrayList class extends AbstractList and implements the List interface. ArrayList supports dynamic arrays that can grow as needed.

Standard Java arrays are of a fixed length. After arrays are created, they cannot grow or shrink, which means that you must know in advance how many elements an array will hold.

Array lists are created with an initial size. When this size is exceeded, the collection is automatically enlarged. When objects are removed, the array may be shrunk.

Following is the list of the constructors provided by the ArrayList class.

Sr.No.

Constructor & Description

1

ArrayList( )

This constructor builds an empty array list.

2

ArrayList(Collection c)

This constructor builds an array list that is initialized with the elements of the collection c.

3

ArrayList(int capacity)

This constructor builds an array list that has the specified initial capacity. The capacity is the size of the underlying array that is used to store the elements. The capacity grows automatically as elements are added to an array list.

Apart from the methods inherited from its parent classes, ArrayList defines the following methods −

Sr.No.

Method & Description

1

void add(int index, Object element)

Inserts the specified element at the specified position index in this list. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index > size()).

2

boolean add(Object o)

Appends the specified element to the end of this list.

3

boolean addAll(Collection c)

Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator. Throws NullPointerException, if the specified collection is null.

4

boolean addAll(int index, Collection c)

Inserts all of the elements in the specified collection into this list, starting at the specified position. Throws NullPointerException if the specified collection is null.

5

void clear()

Removes all of the elements from this list.

6

Object clone()

Returns a shallow copy of this ArrayList.

7

boolean contains(Object o)

Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that (o==null ? e==null : o.equals(e)).

8

void ensureCapacity(int minCapacity)

Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

9

Object get(int index)

Returns the element at the specified position in this list. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index >= size()).

10

int indexOf(Object o)

Returns the index in this list of the first occurrence of the specified element, or -1 if the List does not contain this element.

11

int lastIndexOf(Object o)

Returns the index in this list of the last occurrence of the specified element, or -1 if the list does not contain this element.

12

Object remove(int index)

Removes the element at the specified position in this list. Throws IndexOutOfBoundsException if the index out is of range (index < 0 || index >= size()).

13

protected void removeRange(int fromIndex, int toIndex)

Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive.

14

Object set(int index, Object element)

Replaces the element at the specified position in this list with the specified element. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index >= size()).

15

int size()

Returns the number of elements in this list.

16

Object[] toArray()

Returns an array containing all of the elements in this list in the correct order. Throws NullPointerException if the specified array is null.

17

Object[] toArray(Object[] a)

Returns an array containing all of the elements in this list in the correct order; the runtime type of the returned array is that of the specified array.

18

void trimToSize()

Trims the capacity of this ArrayList instance to be the list's current size.

Example

The following program illustrates several of the methods supported by ArrayList −

Live Demo

import java.util.*;

public class ArrayListDemo {

 

   public static void main(String args[]) {

      // create an array list

      ArrayList al = new ArrayList();

      System.out.println("Initial size of al: " + al.size());

 

      // add elements to the array list

      al.add("C");

      al.add("A");

      al.add("E");

      al.add("B");

      al.add("D");

      al.add("F");

      al.add(1, "A2");

      System.out.println("Size of al after additions: " + al.size());

 

      // display the array list

      System.out.println("Contents of al: " + al);

 

      // Remove elements from the array list

      al.remove("F");

      al.remove(2);

      System.out.println("Size of al after deletions: " + al.size());

      System.out.println("Contents of al: " + al);

   }

}

This will produce the following result −

Output

Initial size of al: 0

Size of al after additions: 7

Contents of al: [C, A2, A, E, B, D, F]

Size of al after deletions: 5

Contents of al: [C, A2, E, B, D]

 

 

1.3 Linked List

The LinkedList class extends AbstractSequentialList and implements the List interface. It provides a linked-list data structure.

Following are the constructors supported by the LinkedList class.

Sr.No.

Constructor & Description

1

LinkedList( )

This constructor builds an empty linked list.

2

LinkedList(Collection c)

This constructor builds a linked list that is initialized with the elements of the collection c.

Apart from the methods inherited from its parent classes, LinkedList defines following methods −

Sr.No.

Method & Description

1

void add(int index, Object element)

Inserts the specified element at the specified position index in this list. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index > size()).

2

boolean add(Object o)

Appends the specified element to the end of this list.

3

boolean addAll(Collection c)

Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator. Throws NullPointerException if the specified collection is null.

4

boolean addAll(int index, Collection c)

Inserts all of the elements in the specified collection into this list, starting at the specified position. Throws NullPointerException if the specified collection is null.

5

void addFirst(Object o)

Inserts the given element at the beginning of this list.

6

void addLast(Object o)

Appends the given element to the end of this list.

7

void clear()

Removes all of the elements from this list.

8

Object clone()

Returns a shallow copy of this LinkedList.

9

boolean contains(Object o)

Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that (o==null ? e==null : o.equals(e)).

10

Object get(int index)

Returns the element at the specified position in this list. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index >= size()).

11

Object getFirst()

Returns the first element in this list. Throws NoSuchElementException if this list is empty.

12

Object getLast()

Returns the last element in this list. Throws NoSuchElementException if this list is empty.

13

int indexOf(Object o)

Returns the index in this list of the first occurrence of the specified element, or -1 if the list does not contain this element.

14

int lastIndexOf(Object o)

Returns the index in this list of the last occurrence of the specified element, or -1 if the list does not contain this element.

15

ListIterator listIterator(int index)

Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index >= size()).

16

Object remove(int index)

Removes the element at the specified position in this list. Throws NoSuchElementException if this list is empty.

17

boolean remove(Object o)

Removes the first occurrence of the specified element in this list. Throws NoSuchElementException if this list is empty. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index >= size()).

18

Object removeFirst()

Removes and returns the first element from this list. Throws NoSuchElementException if this list is empty.

19

Object removeLast()

Removes and returns the last element from this list. Throws NoSuchElementException if this list is empty.

20

Object set(int index, Object element)

Replaces the element at the specified position in this list with the specified element. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index >= size()).

21

int size()

Returns the number of elements in this list.

22

Object[] toArray()

Returns an array containing all of the elements in this list in the correct order. Throws NullPointerException if the specified array is null.

23

Object[] toArray(Object[] a)

Returns an array containing all of the elements in this list in the correct order; the runtime type of the returned array is that of the specified array.

Example

The following program illustrates several of the methods supported by LinkedList −

Live Demo

import java.util.*;

public class LinkedListDemo {

 

   public static void main(String args[]) {

      // create a linked list

      LinkedList ll = new LinkedList();

     

      // add elements to the linked list

      ll.add("F");

      ll.add("B");

      ll.add("D");

      ll.add("E");

      ll.add("C");

      ll.addLast("Z");

      ll.addFirst("A");

      ll.add(1, "A2");

      System.out.println("Original contents of ll: " + ll);

 

      // remove elements from the linked list

      ll.remove("F");

      ll.remove(2);

      System.out.println("Contents of ll after deletion: " + ll);

     

      // remove first and last elements

      ll.removeFirst();

      ll.removeLast();

      System.out.println("ll after deleting first and last: " + ll);

 

      // get and set a value

      Object val = ll.get(2);

      ll.set(2, (String) val + " Changed");

      System.out.println("ll after change: " + ll);

   }

}

This will produce the following result −

Output

Original contents of ll: [A, A2, F, B, D, E, C, Z]

Contents of ll after deletion: [A, A2, D, E, C, Z]

ll after deleting first and last: [A2, D, E, C]

ll after change: [A2, D, E Changed, C]

 

 

1.4 Stacks

1.5 Queues

1.6 Set

A Set is a Collection that cannot contain duplicate elements. It models the mathematical set abstraction.

The Set interface contains only methods inherited from Collection and adds the restriction that duplicate elements are prohibited.

Set also adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set instances to be compared meaningfully even if their implementation types differ.

The methods declared by Set are summarized in the following table −

Sr.No.

Method & Description

1

add( )

Adds an object to the collection.

2

clear( )

Removes all objects from the collection.

3

contains( )

Returns true if a specified object is an element within the collection.

4

isEmpty( )

Returns true if the collection has no elements.

5

iterator( )

Returns an Iterator object for the collection, which may be used to retrieve an object.

6

remove( )

Removes a specified object from the collection.

7

size( )

Returns the number of elements in the collection.

Example

Set has its implementation in various classes like HashSet, TreeSet, LinkedHashSet. Following is an example to explain Set functionality −

Live Demo

import java.util.*;

public class SetDemo {

 

  public static void main(String args[]) {

      int count[] = {34, 22,10,60,30,22};

      Set<Integer> set = new HashSet<Integer>();

      try {

         for(int i = 0; i < 5; i++) {

            set.add(count[i]);

         }

         System.out.println(set);

 

         TreeSet sortedSet = new TreeSet<Integer>(set);

         System.out.println("The sorted list is:");

         System.out.println(sortedSet);

 

         System.out.println("The First element of the set is: "+ (Integer)sortedSet.first());

         System.out.println("The last element of the set is: "+ (Integer)sortedSet.last());

      }

      catch(Exception e) {}

   }

}

This will produce the following result −

Output

[34, 22, 10, 60, 30]

The sorted list is:

[10, 22, 30, 34, 60]

The First element of the set is: 10

The last element of the set is: 60

 

1.7 TreeSet

TreeSet provides an implementation of the Set interface that uses a tree for storage. Objects are stored in a sorted and ascending order.

Access and retrieval times are quite fast, which makes TreeSet an excellent choice when storing large amounts of sorted information that must be found quickly.

Following is the list of the constructors supported by the TreeSet class.

Sr.No.

Constructor & Description

1

TreeSet( )

This constructor constructs an empty tree set that will be sorted in an ascending order according to the natural order of its elements.

2

TreeSet(Collection c)

This constructor builds a tree set that contains the elements of the collection c.

3

TreeSet(Comparator comp)

This constructor constructs an empty tree set that will be sorted according to the given comparator.

4

TreeSet(SortedSet ss)

This constructor builds a TreeSet that contains the elements of the given SortedSet.

Apart from the methods inherited from its parent classes, TreeSet defines the following methods −

Sr.No.

Method & Description

1

void add(Object o)

Adds the specified element to this set if it is not already present.

2

boolean addAll(Collection c)

Adds all of the elements in the specified collection to this set.

3

void clear()

Removes all of the elements from this set.

4

Object clone()

Returns a shallow copy of this TreeSet instance.

5

Comparator comparator()

Returns the comparator used to order this sorted set, or null if this tree set uses its elements natural ordering.

6

boolean contains(Object o)

Returns true if this set contains the specified element.

7

Object first()

Returns the first (lowest) element currently in this sorted set.

8

SortedSet headSet(Object toElement)

Returns a view of the portion of this set whose elements are strictly less than toElement.

9

boolean isEmpty()

Returns true if this set contains no elements.

10

Iterator iterator()

Returns an iterator over the elements in this set.

11

Object last()

Returns the last (highest) element currently in this sorted set.

12

boolean remove(Object o)

Removes the specified element from this set if it is present.

13

int size()

Returns the number of elements in this set (its cardinality).

14

SortedSet subSet(Object fromElement, Object toElement)

Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.

15

SortedSet tailSet(Object fromElement)

Returns a view of the portion of this set whose elements are greater than or equal to fromElement.

Example

The following program illustrates several of the methods supported by this collection −

Live Demo

import java.util.*;

public class TreeSetDemo {

 

   public static void main(String args[]) {

      // Create a tree set

      TreeSet ts = new TreeSet();

    

      // Add elements to the tree set

      ts.add("C");

      ts.add("A");

      ts.add("B");

      ts.add("E");

      ts.add("F");

      ts.add("D");

      System.out.println(ts);

   }

}

This will produce the following result −

Output

[A, B, C, D, E, F]

 

 

1.8 Binary Search Tree (BST)

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

·         The left sub-tree of a node has a key less than or equal to its parent node's key.

·         The right sub-tree of a node has a key greater than to its parent node's key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as −

left_subtree (keys)    node (key)    right_subtree (keys)

Basic Operations

Following are the basic operations of a tree −

·         Search − Searches an element in a tree.

·         Insert − Inserts an element in a tree.

·         Pre-order Traversal − Traverses a tree in a pre-order manner.

·         In-order Traversal − Traverses a tree in an in-order manner.

·         Post-order Traversal − Traverses a tree in a post-order manner.

Node

Define a node having some data, references to its left and right child nodes.

struct node {

   int data;  

   struct node *leftChild;

   struct node *rightChild;

};

Search Operation

Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

Algorithm

struct node* search(int data){

   struct node *current = root;

   printf("Visiting elements: ");

 

   while(current->data != data){

 

      if(current != NULL) {

         printf("%d ",current->data);

     

         //go to left tree

         if(current->data > data){

            current = current->leftChild;

         }  //else go to right tree

         else {               

            current = current->rightChild;

         }

     

         //not found

         if(current == NULL){

            return NULL;

         }

      }    

   }

  

   return current;

}

Insert Operation

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

Algorithm

void insert(int data) {

   struct node *tempNode = (struct node*) malloc(sizeof(struct node));

   struct node *current;

   struct node *parent;

 

   tempNode->data = data;

   tempNode->leftChild = NULL;

   tempNode->rightChild = NULL;

 

   //if tree is empty

   if(root == NULL) {

      root = tempNode;

   } else {

      current = root;

      parent = NULL;

 

      while(1) {               

         parent = current;

     

         //go to left of the tree

         if(data < parent->data) {

            current = current->leftChild;               

            //insert to the left

       

            if(current == NULL) {

               parent->leftChild = tempNode;

               return;

            }

         }  //go to right of the tree

         else {

            current = current->rightChild;

           

            //insert to the right

            if(current == NULL) {

               parent->rightChild = tempNode;

               return;

            }

         }

      }           

   }

}       

 

 

1.9 Heap (Max Heap/Min Heap)

Heap represents a special tree based data structure used to represent priority queue or for heap sort. We'll going to discuss binary heap tree specifically.

Binary heap tree can be classified as a binary tree with two constraints:

·         Completeness - Binary heap tree is a complete binary tree except the last level which may not have all elements but elements from left to right should be filled in.

·         Heapness - All parent nodes should be greater or smaller to their children. If parent node is to be greater than its child then it is called Max heap otherwise it is called Min heap. Max heap is used for heap sort and Min heap is used for priority queue. We're considering Min Heap and will use array implementation for the same.

Basic Operations

Following are basic primary operations of a Min heap which are following.

·         Insert - insert an element in a heap.

·         Get Minimum - get minimum element from the heap.

·         Remove Minimum - remove the minimum element from the heap

Insert Operation

·         Whenever an element is to be inserted. Insert element at the end of the array. Increase the size of heap by 1.

·         Heap up the element while heap property is broken. Compare element with parent's value and swap them if required.

void insert(int value) {           

   size++;

   intArray[size - 1] = value;

   heapUp(size - 1);

}

 

void heapUp(int nodeIndex){

   int parentIndex, tmp;

   if (nodeIndex != 0) {

      parentIndex = getParentIndex(nodeIndex);

      if (intArray[parentIndex] > intArray[nodeIndex]) {

         tmp = intArray[parentIndex];

         intArray[parentIndex] = intArray[nodeIndex];

         intArray[nodeIndex] = tmp;

         heapUp(parentIndex);

      }

   }

}

Get Minimum

Get the first element of the array implementing the heap being root.

int getMinimum(){

   return intArray[0];

}

Remove Minimum

·         Whenever an element is to be removed. Get the last element of the array and reduce size of heap by 1.

·         Heap down the element while heap property is broken. Compare element with children's value and swap them if required.

void removeMin() {

   intArray[0] = intArray[size - 1];

   size--;

   if (size > 0)

      heapDown(0);

}

 

void heapDown(int nodeIndex){

   int leftChildIndex, rightChildIndex, minIndex, tmp;

   leftChildIndex = getLeftChildIndex(nodeIndex);

   rightChildIndex = getRightChildIndex(nodeIndex);

   if (rightChildIndex >= size) {

      if (leftChildIndex >= size)

         return;

      else

         minIndex = leftChildIndex;

   } else {

      if (intArray[leftChildIndex] <= intArray[rightChildIndex])

         minIndex = leftChildIndex;

      else

         minIndex = rightChildIndex;

   }

   if (intArray[nodeIndex] > intArray[minIndex]) {

      tmp = intArray[minIndex];

      intArray[minIndex] = intArray[nodeIndex];

      intArray[nodeIndex] = tmp;

      heapDown(minIndex);

   }

}

Demo Program

HeapDemo.c

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdbool.h>

 

int intArray[10];

int size;

 

bool isEmpty(){

   return size == 0;

}

 

int getMinimum(){

   return intArray[0];

}

 

int getLeftChildIndex(int nodeIndex){

   return 2*nodeIndex +1;

}

 

int getRightChildIndex(int nodeIndex){

   return 2*nodeIndex +2;

}

 

int getParentIndex(int nodeIndex){

   return (nodeIndex -1)/2;

}

 

bool isFull(){

   return size == 10;

}

 

/**

* Heap up the new element,until heap property is broken.

* Steps:

* 1. Compare node's value with parent's value.

* 2. Swap them, If they are in wrong order.

* */

void heapUp(int nodeIndex){

   int parentIndex, tmp;

   if (nodeIndex != 0) {

      parentIndex = getParentIndex(nodeIndex);

      if (intArray[parentIndex] > intArray[nodeIndex]) {

         tmp = intArray[parentIndex];

         intArray[parentIndex] = intArray[nodeIndex];

         intArray[nodeIndex] = tmp;

         heapUp(parentIndex);

      }

   }

}

 

/**

* Heap down the root element being least in value,until heap property is broken.

* Steps:

* 1.If current node has no children, done. 

* 2.If current node has one children and heap property is broken,

* 3.Swap the current node and child node and heap down.

* 4.If current node has one children and heap property is broken, find smaller one 

* 5.Swap the current node and child node and heap down.

* */

void heapDown(int nodeIndex){

   int leftChildIndex, rightChildIndex, minIndex, tmp;

   leftChildIndex = getLeftChildIndex(nodeIndex);

   rightChildIndex = getRightChildIndex(nodeIndex);

   if (rightChildIndex >= size) {

      if (leftChildIndex >= size)

         return;

      else

         minIndex = leftChildIndex;

   } else {

      if (intArray[leftChildIndex] <= intArray[rightChildIndex])

         minIndex = leftChildIndex;

      else

         minIndex = rightChildIndex;

   }

   if (intArray[nodeIndex] > intArray[minIndex]) {

      tmp = intArray[minIndex];

      intArray[minIndex] = intArray[nodeIndex];

      intArray[nodeIndex] = tmp;

      heapDown(minIndex);

   }

}

 

void insert(int value) {           

   size++;

   intArray[size - 1] = value;

   heapUp(size - 1);

}

 

void removeMin() {

   intArray[0] = intArray[size - 1];

   size--;

   if (size > 0)

      heapDown(0);

}

 

main()

{

   /*                     5                //Level 0

   *

   */

   insert(5);

   /*                     1                //Level 0

   *                     |

   *                 5---|                //Level 1

   */  

   insert(1);

   /*                     1                //Level 0

   *                     |

   *                 5---|---3            //Level 1

   */

   insert(3);

   /*                     1                //Level 0

   *                     |

   *                 5---|---3            //Level 1

   *                 |

   *              8--|                    //Level 2

   */

   insert(8);

   /*                     1                //Level 0

   *                     |

   *                 5---|---3            //Level 1

   *                 |

   *              8--|--9                 //Level 2

   */

   insert(9);

   /*                     1                 //Level 0

   *                     |

   *                 5---|---3             //Level 1

   *                 |       |

   *              8--|--9 6--|             //Level 2

   */

   insert(6);

   /*                     1                 //Level 0

   *                     |

   *                 5---|---2             //Level 1

   *                 |       |

   *              8--|--9 6--|--3          //Level 2

   */

   insert(2);

 

   printf("%d", getMinimum());

 

   removeMin();

   /*                     2                 //Level 0

   *                     |

   *                 5---|---3             //Level 1

   *                 |       |

   *              8--|--9 6--|             //Level 2

   */

   printf("\n%d", getMinimum());  

}

If we compile and run the above program then it would produce following result:

1

2

 

 

1.10 Graph

A graph is an abstract notation used to represent the connection between pairs of objects. A graph consists of −

·         Vertices − Interconnected objects in a graph are called vertices. Vertices are also known as nodes.

·         Edges − Edges are the links that connect the vertices.

There are two types of graphs −

·         Directed graph − In a directed graph, edges have direction, i.e., edges go from one vertex to another.

·         Undirected graph − In an undirected graph, edges have no direction.

Graph Coloring

Graph coloring is a method to assign colors to the vertices of a graph so that no two adjacent vertices have the same color. Some graph coloring problems are −

·         Vertex coloring − A way of coloring the vertices of a graph so that no two adjacent vertices share the same color.

·         Edge Coloring − It is the method of assigning a color to each edge so that no two adjacent edges have the same color.

·         Face coloring − It assigns a color to each face or region of a planar graph so that no two faces that share a common boundary have the same color.

Chromatic Number

Chromatic number is the minimum number of colors required to color a graph. For example, the chromatic number of the following graph is 3.

The concept of graph coloring is applied in preparing timetables, mobile radio frequency assignment, Suduku, register allocation, and coloring of maps.

Steps for graph coloring

·         Set the initial value of each processor in the n-dimensional array to 1.

·         Now to assign a particular color to a vertex, determine whether that color is already assigned to the adjacent vertices or not.

·         If a processor detects same color in the adjacent vertices, it sets its value in the array to 0.

·         After making n2 comparisons, if any element of the array is 1, then it is a valid coloring.

Pseudocode for graph coloring

begin

 

   create the processors P(i0,i1,...in-1) where 0_iv < m, 0 _ v < n

   status[i0,..in-1] = 1

 

   for j varies from 0 to n-1 do

      begin

   

         for k varies from 0 to n-1 do

         begin

            if aj,k=1 and ij=ikthen

            status[i0,..in-1] =0

         end

     

      end

      ok = ΣStatus

   

   if ok > 0, then display valid coloring exists

   else

      display invalid coloring

     

end

Minimal Spanning Tree

A spanning tree whose sum of weight (or length) of all its edges is less than all other possible spanning tree of graph G is known as a minimal spanning tree or minimum cost spanning tree.

To implement the minimum cost-spanning tree, the following two methods are used −

·         Prim’s Algorithm

·         Kruskal’s Algorithm

Prim's Algorithm

Prim’s algorithm is a greedy algorithm, which helps us find the minimum spanning tree for a weighted undirected graph. It selects a vertex first and finds an edge with the lowest weight incident on that vertex.

Steps of Prim’s Algorithm

·         Select any vertex, say v1 of Graph G.

·         Select an edge, say e1 of G such that e1 = v1 v2 and v1 ≠ v2 and e1 has minimum weight among the edges incident on v1 in graph G.

·         Now, following step 2, select the minimum weighted edge incident on v2.

·         Continue this till n–1 edges have been chosen. Here n is the number of vertices. Kruskal's Algorithm

Kruskal’s algorithm is a greedy algorithm, which helps us find the minimum spanning tree for a connected weighted graph, adding increasing cost arcs at each step. It is a minimum-spanning-tree algorithm that finds an edge of the least possible weight that connects any two trees in the forest.

Steps of Kruskal’s Algorithm

·         Select an edge of minimum weight; say e1 of Graph G and e1 is not a loop.

·         Select the next minimum weighted edge connected to e1.

·         Continue this till n–1 edges have been chosen. Here n is the number of vertices. Shortest Path Algorithm

Shortest Path algorithm is a method of finding the least cost path from the source node(S) to the destination node (D). Here, we will discuss Moore’s algorithm, also known as Breadth First Search Algorithm.

Moore’s algorithm

·         Label the source vertex, S and label it i and set i=0.

·         Find all unlabeled vertices adjacent to the vertex labeled i. If no vertices are connected to the vertex, S, then vertex, D, is not connected to S. If there are vertices connected to S, label them i+1.

·         If D is labeled, then go to step 4, else go to step 2 to increase i=i+1.

·         Stop after the length of the shortest path is found.

 

 

2 Algorithms

2.1 Sorting

2.2 Searching

2.3 Tree Traversals

In this section we will see different traversal algorithms to traverse keys present in binary search tree. These traversals are Inorder traversal, Preorder traversal, Postorder traversal and the level order traversal.

Suppose we have one tree like this −

 

The Inorder traversal sequence will be like − 5 8 10 15 16 20 23

The Preorder traversal sequence will be like − 10 5 8 16 15 20 23

The Postorder traversal sequence will be like − 8 5 15 23 20 16 10

The Level-order traversal sequence will be like − 10, 5, 16, 8, 15, 20, 23

Algorithm

inorderTraverse(root):

Begin

   if root is not empty, then

      inorderTraversal(left of root)

      print the value of root

      inorderTraversal(right of root)

   end if

End

preorderTraverse(root):

Begin

   if root is not empty, then

      print the value of root

      preorderTraversal(left of root)

      preorderTraversal(right of root)

   end if

End

postorderTraverse(root):

Begin

   if root is not empty, then

      postorderTraversal(left of root)

      postorderTraversal(right of root)

      print the value of root

   end if

End

levelOrderTraverse(root):

Begin

   define queue que to store nodes

   insert root into the que.

   while que is not empty, do

      item := item present at front position of queue

      print the value of item

      if left of the item is not null, then

         insert left of item into que

      end if

      if right of the item is not null, then

         insert right of item into que

      end if

      delete front element from que

   done

End

Example

#include<iostream>

#include<queue>

using namespace std;

class node{

   public:

      int h_left, h_right, bf, value;

      node *left, *right;

};

class tree{

   private:

      node *get_node(int key);

   public:

      node *root;

      tree(){

         root = NULL; //set root as NULL at the beginning

      }

      void inorder_traversal(node *r);

      void preorder_traversal(node *r);

      void postorder_traversal(node *r);

      void levelorder_traversal(node *r);

      node *insert_node(node *root, int key);

};

node *tree::get_node(int key){

   node *new_node;

   new_node = new node; //create a new node dynamically

   new_node->h_left = 0; new_node->h_right = 0;

   new_node->bf = 0;

   new_node->value = key; //store the value from given key

   new_node->left = NULL; new_node->right = NULL;

   return new_node;

}

void tree::inorder_traversal(node *r){

   if(r != NULL){ //When root is present, visit left - root - right

      inorder_traversal(r->left);

      cout << r->value << " ";

      inorder_traversal(r->right);

   }

}

void tree::preorder_traversal(node *r){

   if(r != NULL){ //When root is present, visit left - root - right

      cout << r->value << " ";

      preorder_traversal(r->left);

      preorder_traversal(r->right);

   }

}

void tree::postorder_traversal(node *r){

   if(r != NULL){ //When root is present, visit left - root - right

      postorder_traversal(r->left);

      postorder_traversal(r->right);

      cout << r->value << " ";

   }

}

void tree::levelorder_traversal(node *root){

   queue <node*> que;

   node *item;

   que.push(root); //insert the root at first

   while(!que.empty()){

      item = que.front(); //get the element from the front end

      cout << item->value << " ";

      if(item->left != NULL) //When left child is present, insert into queue

         que.push(item->left);

      if(item->right != NULL) //When right child is present, insert into queue

         que.push(item->right);

      que.pop(); //remove the item from queue

   }

}

node *tree::insert_node(node *root, int key){

   if(root == NULL){

      return (get_node(key)); //when tree is empty, create a node as root

   }

   if(key < root->value){ //when key is smaller than root value, go to the left

      root->left = insert_node(root->left, key);

   }else if(key > root->value){ //when key is greater than root value, go to the right

      root->right = insert_node(root->right, key);

   }

   return root; //when key is already present, do not insert it again

}

main(){

   node *root;

   tree my_tree;

   //Insert some keys into the tree.

   my_tree.root = my_tree.insert_node(my_tree.root, 10);

   my_tree.root = my_tree.insert_node(my_tree.root, 5);

   my_tree.root = my_tree.insert_node(my_tree.root, 16);

   my_tree.root = my_tree.insert_node(my_tree.root, 20);

   my_tree.root = my_tree.insert_node(my_tree.root, 15);

   my_tree.root = my_tree.insert_node(my_tree.root, 8);

   my_tree.root = my_tree.insert_node(my_tree.root, 23);

   cout << "In-Order Traversal: ";

   my_tree.inorder_traversal(my_tree.root);

   cout << "\nPre-Order Traversal: ";

   my_tree.preorder_traversal(my_tree.root);

   cout << "\nPost-Order Traversal: ";

   my_tree.postorder_traversal(my_tree.root);

   cout << "\nLevel-Order Traversal: ";

   my_tree.levelorder_traversal(my_tree.root);

}

Output

In-Order Traversal: 5 8 10 15 16 20 23

Pre-Order Traversal: 10 5 8 16 15 20 23

Post-Order Traversal: 8 5 15 23 20 16 10

Level-Order Traversal: 10 5 16 8 15 20 23

 

 

2.4 Breadth-First Search

Breadth First Search or BFS for a Graph

graphic

The Breadth First Search (BFS) traversal is an algorithm, which is used to visit all of the nodes of a given graph. In this traversal algorithm one node is selected and then all of the adjacent nodes are visited one by one. After completing all of the adjacent vertices, it moves further to check another vertices and checks its adjacent vertices again.

To implement this algorithm, we need to use the Queue data structure. All the adjacent vertices are added into the queue, when all adjacent vertices are completed, one item is removed from the queue and start traversing through that vertex again.

In Graph sometimes, we may get some cycles, so we will use an array to mark when a node is visited already or not.

Input - The Adjacency matrix of the graph.

A B C D E F

A 0 1 1 1 0 0

B 1 0 0 1 1 0

C 1 0 0 1 0 1

D 1 1 1 0 1 1

E 0 1 0 1 0 1

F 0 0 1 1 1 0

Output - BFS Traversal: B A D E C F

Algorithm

bfs(vertices, start)

Input − The list of vertices, and the start vertex.

Output − Traverse all of the nodes, if the graph is connected.

Begin

   define an empty queue que

   at first mark all nodes status as unvisited

   add the start vertex into the que

   while que is not empty, do

      delete item from que and set to u