Heap in STL

  HEAP DATA STRUCTURE


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<int>v1;
  v1.push_back(10);
  v1.push_back(5);
  v1.push_back(8);
  v1.push_back(48);
  v1.push_back(20);
  v1.push_back(6);
  v1.push_back(1);


Making Heap 

make_heap(v1.begin(),v1.end());
This will convert this vector into a heap
cout<<v1.front()<<endl;
Sort Heap -> After this the operation the container is sorted and no longer a Heap
sort_heap(v1.begin(),v1.end());
vector<int>::iterator it ;
for(it=v1.begin();it!=v1.end();it++)
{
cout<<*it<<" ";
}
cout<<endl;
Insert new elements in Heap
push_heap() :- This function is used to insert elements into heap. The size of the heap is increased by 1. New element is placed appropriately in the heap.


 pop_heap() :- This function is used to delete the maximum element of the heap. The size of heap is decreased by 1. The heap elements are reorganized accordingly after this operation.
pop_heap() should be followed by a v1.pop_back()  otherwise it won't actually be popped. Coz pop_heap() just shifts the largest element to the end position . pop_back() reduces the size of the heap by one.
 v1.push_back(50);
     
    // using push_heap() to reorder elements
    push_heap(v1.begin(), v1.end());
     
    // Displaying the maximum element of heap
    // using front()
    cout << "The maximum element of heap after push is : ";
    cout << v1.front() << endl;
     
     // using pop_heap() to delete maximum element
    pop_heap(v1.begin(), v1.end());
    v1.pop_back();
     
    // Displaying the maximum element of heap
    // using front()
    cout << "The maximum element of heap after pop is : ";
    cout << v1.front() << endl;

}

output :
48
1 5 6 8 10 20 48
The maximum element of heap after push is : 50
The maximum element of heap after pop is : 6

is_heap() :- This function is used to check whether the container is heap or not. Generally, in most implementations, the reverse sorted container is considered as heap. Returns true if container is heap else returns false.

  is_heap_until() :- This function returns the iterator to the position till the container is the heap. Generally, in most implementations, the reverse sorted container is considered as heap.

Learning Graphs

Representation :

Using adjacency list :


BFS and DFS 
// Program to print BFS traversal from a given source vertex. BFS(int s) 
// traverses vertices reachable from s.
#include<iostream>
#include <list>

using namespace std;

// This class represents a directed graph using adjacency list representation
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // Pointer to an array containing adjacency lists

/*
adj = new list[V];
If you use simply list adj[V] system creates an array of list with size V, so your list constructor will get call V times.
new operator allocates memory and invokes the constructor.

So this statement list* adj= new list[V] allocates memory for V times the size of object of class list and invokes constructor of class list V times, and assigns the starting of the memory location to variable adj.

This kind of statement
x = new X[N];
assigns the result of the expression on the right hand side of the = to x.
So, you are dynamically allocating an array of V objects of type list, ans assigning a pointer to the first element to adj.
*/ 

    void DFSUtil(int v, bool visited[]);  // A function used by DFS
public:
    Graph(int V);  // Constructor
    void addEdge(int v, int w); // function to add an edge to graph
    void BFS(int s,int check);  // prints BFS traversal from a given source s
    void DFS(int v);    // DFS traversal of the vertices reachable from v 
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

void Graph::BFS(int s,int  check)
{
    int ans =1;
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;

    // Create a queue for BFS
    list<int> queue;

    // Mark the current node as visited and enqueue it
    visited[s] = true; if(s==check){ans =0;}
    queue.push_back(s);

    // 'i' will be used to get all adjacent vertices of a vertex
    list<int>::iterator i;

    while(!queue.empty())
    {
        // Dequeue a vertex from queue and print it
        s = queue.front();
         if(s==check){ans =0;}
        cout << s << " ";
        queue.pop_front();

        // Get all adjacent vertices of the dequeued vertex s
        // If a adjacent has not been visited, then mark it visited
        // and enqueue it
        for(i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            if(!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }//cout<<endl;
    }cout<<endl<<ans<<endl;
}
void Graph::DFSUtil(int v, bool visited[])
{
    // Mark the current node as visited and print it
    visited[v] = true;
    cout << v << " ";

    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}

// DFS traversal of the vertices reachable from v. 
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function to print DFS traversal
    DFSUtil(v, visited);
}


// Driver program to test methods of graph class
int main()
{

     int nodes, max_edges, origin, destin;
   // cout<<"Enter number of nodes: ";
    cin>>nodes;
    Graph g(nodes);
    max_edges = nodes * (nodes - 1);
    for (int i = 0; i < max_edges; i++)
    {
       
        cin>>origin>>destin;
        
        if((origin == -1) && (destin == -1))
            break;
         g.addEdge(origin, destin);
    }
   
    int verty,checky;
    cin>>verty>>checky;

    g.BFS(verty,checky);
    g.DFS(verty);
}

There is something called as topological sorting , so that you can check which job is scheduled first or next . you can check the order of dfs by  this :

// A C++ program to print topological sorting of a DAG

#include <iostream>

#include <stdio.h>

#include <list>

#include <stack>

using namespace std;

// Class to represent a graph

class Graph

{

    int V;    // No. of vertices'

    // Pointer to an array containing adjacency listsList

    list<int> *adj;

    // A function used by topologicalSort

    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);

public:

    Graph(int V);   // Constructor

     // function to add an edge to graph

    void addEdge(int v, int w);

    // prints a Topological Sort of the complete graph

    void topologicalSort();

};

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Add w to v’s list.

}

// A recursive function used by topologicalSort

void Graph::topologicalSortUtil(int v, bool visited[], 

                                stack<int> &Stack)

{

    // Mark the current node as visited.

    visited[v] = true;

    // Recur for all the vertices adjacent to this vertex

    list<int>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

        if (!visited[*i])

            topologicalSortUtil(*i, visited, Stack);

    // Push current vertex to stack which stores result

    Stack.push(v);

}

// The function to do Topological Sort. It uses recursive 

// topologicalSortUtil()

void Graph::topologicalSort()

{

    stack<int> Stack;

    // Mark all the vertices as not visited

    bool *visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

    // Call the recursive helper function to store Topological

    // Sort starting from all vertices one by one

    for (int i = 0; i < V; i++)

      if (visited[i] == false)

        topologicalSortUtil(i, visited, Stack);

    // Print contents of stack

    while (Stack.empty() == false)

    {

        cout << Stack.top() << " ";

        Stack.pop();

    }

}

// Driver program to test above functions

int main()

{

    // Create a graph given in the above diagram

    int V,i,j,k;

    scanf("%d",&V);

    Graph g(V+1);

    for(i=1;i<V;i++)

    {

        scanf("%d%d",&j,&k);

        g.addEdge(j,k);

    }

    cout << "Following is a Topological Sort of the given graph \n";

    g.topologicalSort();

    return 0;

}

There  is a way to traverse a rectangular maze using DFS :

function DFS(x, y, visited, n, m)

    if (x ≥ n OR y ≥ m)

        return

    if(x < 0 OR y < 0)

        return

    if(visisted[x][y] == True)

        return

    visited[x][y] = True

    DFS(x-1, y-1, visited, n, m)

    DFS(x-1, y, visited, n, m)

    DFS(x-1, y+1, visited, n, m)

    DFS(x, y-1, visited, n, m)

    DFS(x, y+1, visited, n, m)

    DFS(x+1, y-1, visited, n, m)

    DFS(x+1, y, visited, n, m)

    DFS(x+1, y+1, visited, n, m)

Difference between a graph and a tree :

In a graph there can be back edge , forward edge , cross edge , tree edge .

DFS of a graph gives you a tree. And if there are more components which are disconnected, then DFS give a tree forest.

1.In a tree  there is aunique  path from every single  vertex to other vertices. Also it is not necessary that degree of all the vertices of a tree is either 1 or 2.

2.There isn't any cycle in a tree.

 How to detect cycle in an undirected graph?

We can either use BFS or DFS. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle.

3.If we take the sum of all the degrees, each edge will be counted twice. Hence, for a tree with n vertices and n – 1 edges, sum of all degrees should be 2 * (n – 1).

4.Tree has exactly n-1 edges while there is no such constraint for graph.

Babylonian algorithm of finding square root

Finding square root of a number whether its perfect square or not is simple with sqrt(n) function , but what if you have to implement it on your own?

 There are several ways for it. I will tell you about 2 methods:

1. Using Binary Search in O(log N)  time complexity

2. Babylonian Method of O(log(log N)).

1. 
   Using Binary Search

   float squareroot( float n)


{    
    // Base cases
    if (n == 0 || n == 1) 
       return n;

    // Do Binary Search for floor(sqrt(x))
     float start = 1, end = n, ans;   
    while (start <= end) 
    {       
    cout<<start<<"    "<<end<<endl; 
        float mid = (start + end) / 2;

        // If x is a perfect square

      /* It is very important to see that mid*mid can overflow, so rather than doing (mid*mid) do
     if(mid<=x/mid)      */

          if(mid==n/mid)
            return mid;

        // Since we need floor, we update answer when mid*mid is 
        // smaller than x, and move closer to sqrt(x)
         if(mid<=n/mid)
        {
            start = mid + 1;
            ans = mid;
        } 
        else // If mid*mid is greater than x
            end = mid - 1;        
    }
    return (ans+1);
}
   





2.  

float squareRoot(float n)
{
  /*We are using n itself as initial approximation
   This can definitely be improved */
  float x = n;
  float y = 1;
  float e = 0.000001; /* e decides the accuracy level*/
  while(x - y > e)
  {
    x = (x + y)/2;
    y = n/x;
  }
  return x;

}