Learn Programming online

Started Two months Online Programming Classes for XI, XII (all boards), B.Sc.(CS/IT), BCA, M.Sc.(CS/IT), MCA.

Programming Languages

1. C

2. C++

3. Python Basics

4. Python for Data Science

5. R programming

Web Designing

1. HTML

2. CSS

3. PHP

Theory Papers

1. DBMS

2. OS

3. Data Structure using C/C++

New Batches starting from 25 May. Limited Seats. 

Comment Below your contact details(name, email-id and mobile number) if your are interested.

Doubts / Queries

Comment below your queries, doubts or you want to understand any concept related with Data Structure again. 

Heap Sort Algorithm

What is heap?

A heap is defined as a complete binary tree with n nodes such that

1. Value of each node is less than or equal to the root. When root of the binary tree is the biggest number in the heap. This type of heap is known as max Heap  or descending Heap.


2. Value of each node is greater than or equal to the root. When root of the binary tree is the smallest number in the heap. This type of heap is known as min Heap  or ascending Heap.

Each node in the heap corresponds to an element of the array, with the root node corresponding to the element with index 0 in the array. Considering a node corresponding to index i, then its left child has index (2*i + 1) and its right child has index (2*i + 2).

Heap can be used to sort the data in ascending and descending order. The method is known as Heap Sort. Heap Sort involves two basic step

1. Build Heap

•      Create max heap to sort the data in ascending order
•      Create min Heap to sort data in descending order

2. Heapify


ALGORITHM 
    Heapify(A, i){
        l <- left(i)
        r <- right(i)
        if l <= heapsize[A] and A[l] > A[i]
            then largest <- l
            else largest <- i
        if r <= heapsize[A] and A[r] > A[largest]
            then largest <- r
        if largest != i
            then swap A[i] <-> A[largest]
                Heapify(A, largest)
    }

    Buildheap(A){
        heapsize[A] <- length[A]
        for i <- |length[A]/2| downto 1
            do Heapify(A, i)
    }

    Heapsort(A){
        Buildheap(A)
        for i <- length[A] downto 2
            do swap A[1] <-> A[i]
            heapsize[A] <- heapsize[A] - 1
            Heapify(A, 1)
    }

Kruskal Algorithm

DEFINITION - Minimum Cost Spanning Tree

Let G=(V,E,W) be any weighted graph. Then a spanning tree whose cost is minimum is called minimum spanning tree. The cost of the spanning tree is defined as the sum of the costs of the edges in that tree.

Kruskal’s Algorithm

Kruskal’s Algorithm uses greedy approach to select an edge with a minimum cost that doesn't result in cycle when added to already selected edges. Time complexity of Kruskal’s algorithm is o(n+eloge).
In this method all the edges are arranged in the increasing order of the cost. Now select one by one the edges with minimum cost but edges are accepted if and only if there is no cycle. All the other edges having high cost or cycle is formed are rejected.

The steps involved are

Step 1: Construct a min heap of edges on the basis of ascending order of cost of edges.

Step 2: Delete edge from heap and add to minimum cost spanning tree T if no cycle

Step 3: Repeat until e=n-1 or heap is empty

EXAMPLE

Prim's Method

DEFINITION - Minimum Cost Spanning Tree

Let G=(V,E,W) be any weighted graph. Then a spanning tree whose cost is minimum is called minimum spanning tree. The cost of the spanning tree is defined as the sum of the costs of the edges in that tree.

Prim's Algorithm 

In Prim’s algorithm, greedy criterion is used to determine the next edge that have minimum cost. It has a time complexity of O(n²). The steps to find minimum cost spanning tree using Prim’s algorithm is

The steps involved are

Step 1: Select the minimum cost edge and include in minimum spanning tree T

Step 2: Select adjacent edges to T which is minimum in cost and add to T

Step 3: Repeat Step 1 and 2 for n-1 edges and no cycle

EXAMPLE

Introduction of Graphs

A graph consists of two sets V and E.

• V is finite and non empty set of vertices
• E is a set of edges connecting two vertices. 

Graphs can be directed or undirected

Directed Graph: If all the edges of a graph have specific direction then this type of graph is called directed graph.For Example: V = {1,2,3,4} and E={(1,2), (2,3), (2,4), (3,1), (4,1), (4,3)}Then Directed Graph G={V,E} represented as

Undirected Graph: If all the edges of the graphs has no specific direction then this type of graph  is known as undirected graph.For Example: V = {1,2,3,4} and E={(1,2), (1,3),(1,4), (2,1),(2,3),(2,4), (3,1),(3,2),(3,4), (4,1),(4,2), (4,3)}Then Undirected Graph G={V,E} represented as

 Representation of Graph

Adjacency Matrix: It is the two dimensional array or matrix representation of graph. In the matrix, the element a(i,j)= 0 if there is no edge between vertex i and j; the element a(i,j)=1 if there is an edge between vertex i and j. It is also known as Static Representation of graph.

For Example : Consider the following Directed Graph.  The Adjacent Matrix is 

        1    2     3     4

1      0    1     0     0

2      0    0     0     1

3      0    0     0     0

4      1    0     1     0




Consider the following Undirected Graph.  The Adjacent Matrix is  

        1    2     3     4

1      0    1     0     1

2      1    0     0     1

3      0    0     0     0

4      1    1     1     0

Adjacency List: It is the list representation of graphs. In this representation, if there are n vertices then there are n linked list for each vertex of graph. It is also known as Dynamic Representation of graph.

Traversing a Graphs

Exploring each vertex of the graph is known as traversing a graph. The order in which we explored the vertices depend upon what kind of data structure is used.  The two common graph traversal method are

1. Breadth First Search (BFS)
2. Depth First Search (DFS)

Spanning Tree 

A tree T is a spanning tree of a graph G={V,E} if every vertex of G belongs to an edge in T and theedges in T form a tree. Details...

Graph Traversal - Breadth First Search

Breadth First Search can be used to find the shortest distance between some starting vertex and remaining vertex of the graph. In this method, all the vertices are stored in a Queue and each vertex of the graph is visited or explored once. The oldest vertex (added first) in the Queue is explored first. To traverse the graph using breadth first search, Adjacent List of a graph is created first.

EXAMPLE

For Example : Consider the following Graph

The Adjacent List is

11 -> 12,18,13

12-> 11,14,15

13-> 11,16,17

14-> 12,18

15-> 12,18

16-> 13,18

17-> 13,18

18-> 14,15,11,16,17

Let us suppose that starting node is 11, The steps to traverse graph using Breadth First Search Is

Step 1: Add 11 to queue

Front: 1                    Queue: 11

Rear:1

Step 2: Delete element at Front  position (11) and add all the adjacent nodes of deletd not that are not visited.

Front: 2                    Queue: X,12, 18, 13

Rear:4

Step 3: Delete element at Front position (12) and add all the adjacent nodes of deletd not that are not visited.

Front: 3                    Queue: X,X,18, 13, 14, 15           

Rear:6

 11 already visited; i.e. in Queue or deleted

Step 4: Delete element at Front position (18) and add all the adjacent nodes of deletd not that are not visited.

Front: 4                    Queue: X,X,X,13, 14, 15, 16,17        

Rear:8

11,14,15 already visited; i.e. in Queue or deleted

Step 5: Delete element at Front position (13) and add all the adjacent nodes of deletd not that are not visited.

Front: 5                    Queue: X,X,X,X, 14, 15, 16,17        

Rear:8

No vertex added becoz 11,16,17 already visited; i.e. in Queue or deleted

Step 6: Delete element at Front position (14) and add all the adjacent nodes of deletd not that are not visited.

Front: 6                    Queue: X,X,X,X, X, 15, 16,17       

Rear:8

No vertex added becoz 12 and 18 already visited; i.e. in Queue or deleted

Step 7: Delete element at Front position (15) and add all the adjacent nodes of deletd not that are not visited.

Front: 7                    Queue: X,X,X,X, X,X,16,17      

Rear:8

No vertex added becoz 12 and 18 already visited; i.e. in Queue or deleted

Step 8: Delete element at Front position (16) and add all the adjacent nodes of deletd not that are not visited.

Front: 8                    Queue: X,X,X,X, X,X,X,17      

Rear:8

No vertex added becoz 13 and 18 already visited; i.e. in Queue or deleted

Step 9: Delete element at Front position (17) and add all the adjacent nodes of deletd not that are not visited.

Front: 8                   Queue: X,X,X,X, X,X,X,X      

Rear:8

No vertex added becoz 13 and 18 already visited; i.e. in Queue or deleted

Queue EMPTY. STOP.

Therefore Breadth First Search is 11,12,18,13,14,15,16,17

ALGORITHM

Step 1: Initialize all the vertices and create adjacent list.

Step 2: Put Starting vertex in Queue.

Step 3: Repeat Step 4 and 5 until Queue is empty.

Step 4: Remove front node from the Queue.

Step 5: Add to the rear of the Queue all the neighbors of the deleted node that are not visited or added in a Queue.

Step 6: Exit

APPLICATIONS

1. Used to test whether graph is connected or not
2. To find the cycles in the graphs
3. To find the path with minimum number of edges between start vertex and current vertex or reporting that no such path exists.