Max HeapSort Algorithm and its Application in implementing Max Prioritiy Queues

Operations supported on Max-Priority Queues are:
1)  Max : Returns maximum element currently in queue in O(1) time
2)  ExtractMax : Returns and removes maximum element currently
                         in queue in O(lg(n)) time
3) Insert: Inserts given element in queue in O(lg(n)) time
4) IncreasePriority : Increases priority of element at given index in
                             O(lg(n)) time
5) IncreasePriority : Decrease priority of element at given index in
                             O(lg(n)) time

All order statistics mentioned above is in worst case

#include <stdio.h>
#include <stdlib.h>

#define LEFT(i) ((i<<1)+1)
#define RIGHT(i) ((i<<1)+2)
#define PARENT(i) (i>>1)

void Swap(int *i,int *j);
void MaintainMaxHeap(int a[],int index,int size);

void BuildMaxHeap(int a[],int size);

void HeapSort(int a[],int size);

int Max(int a[],int numValidElements,int size)
{
    if(numValidElements>0)
        return a[0];
    else
            fprintf(stderr,"Error\n");
}


/*
Number of numValidElements count should be decremented 
by caller itself.
*/
int ExtractMax(int a[],int numValidElements,int size)
{
    if(numValidElements>0)
    {
        Swap(&a[0],&a[--numValidElements]);
        MaintainMaxHeap(a,0,numValidElements);
        return a[numValidElements];
    }
    else
        fprintf(stderr,"Error\n");  
}


void IncreasePriority(int a[],int index,int newPriority,int numValidElements)
{
    if(a[index]<newPriority)
    {
        a[index]=newPriority;
        while(index>0 && a[index]>a[PARENT(index)])
        {
            Swap(&a[index],&a[PARENT(index)]);
            index=PARENT(index);
        }
    }
    else
    {
        fprintf(stderr,"Error in IncreasePriority\n");
    }
}


void DecreasePriority(int a[],int index,int newPriority,int numValidElements)
{
    if(a[index]>newPriority)
    {
        a[index]=newPriority;
        MaintainMaxHeap(a,index,numValidElements);
    }
    else
    {
        fprintf(stderr,"Error in DecreasePriority\n");
    }
}


/*
Its upto caller to increase numValidElements after 
*/
void Insert(int a[],int priority,int numValidElements,int size)
{
    if(numValidElements<size)
    {
        a[numValidElements]=INFINITE;
        IncreasePriority(a,numValidElements,priority,size);
    }
    else
        fprintf(stderr,"Queue Overflow\n");

}


/*
Pre: Subtrees of node at position index are already both max_heaps 
       and size is number of elements in an array 
Post: Element at position index is inserted properly so that tree rooted 
        at index is max_heap 
*/
void MaintainMaxHeap(int a[],int index,int size)
{
        int left=LEFT(index);
        int right=RIGHT(index);
        int max=index;
        if(left < size && a[left]>a[max])
                max=left;
        if(right < size && a[right]>a[max])
                max=right;
        if(max!=index)
       {
                Swap(&a[max],&a[index]);
                MaintainMaxHeap(a,max,size);
       }
}


/*
Post: Elements of array a from index [0,size-1] are 
         arranged so as to form max heap
*/
void BuildMaxHeap(int a[],int size)
{
        int i;
        // Elements from (size/2) to (size-1) are all leaves 
        for(i=size/2-1;i>=0;i--)
        MaintainMaxHeap(a,i,size);
}


void HeapSort(int a[],int size)
{
        int i;
        BuildMaxHeap(a,size);
        for(i=size-1;i>0;i--)
       {
                // Max element in array is at index=0
               Swap(&a[0],&a[i]);
               MaintainMaxHeap(a,0,--size);
       }
}

void Swap(int *i,int *j)
{
        int temp=*i;
        *i=*j;
        *j=temp;
}

NOTES: 
1)Above implementation was for implementing max priority queues, similarly minimum priority queues could also be implemented using min heaps. 
2)Error Handling is done simply by printing message.In any practical application it should be thoroughly done. Thank you.

1) Reversing k elements of a singly linked list at a time (Amazon Test Question) and 2) Finding last kth elements of singly linked list Efficiently

Suppose our linked list contains integer values and is described as:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
and if we want to reverse 2 elements at a time then modified linked list should be:
2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7
and if we want to reverse 3 elements at a time then modified linked list should be:
3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8
Here in case where k=3 last 2 elements are not reversed because 2<3.

We will use recursive algorithm to implement above reversal. Assume List Node's defination as:

//Node Data
typedef struct _DATA
{
int key;

}DATA,*PDATA;

//Node Struct
typedef struct _NODE
{
DATA item;
struct _node *pnext;

}NODE,*PNODE;

//
//Helper functions
//

PNODE NewNode(DATA item);
PNODE InsertAtStart(PNODE phead,DATA item);
PNODE DeleteAtStart(PNODE phead,PDATA pdata);
void Traverse(PNODE phead);
void DeleteList(PNODE phead);

//Reverses linked list pointed by phead
PNODE Reverse(PNODE phead);

//
// First reverse first k nodes then reverse N-k nodes  
// recursively where N=total size of  list
//
PNODE ReverseKNodesAtATime(PNODE phead,int k)
{
PNODE temp=phead;
int count=k;
     
        // Move to kth node from starting
while(temp && --count)
{
temp=temp->pnext;
}
if(temp)
{
                /*remaining list containing N-k  nodes head*/
PNODE nextstart=temp->pnext;
                 
                /* set end of list of first k nodes to NULL*/
temp->pnext=NULL;                                    

                 /* newHead is head of list of first k nodes after reversal*/
                PNODE newHead=Reverse(phead);                
                                                                                            
               /*Now phead points to end of first k nodes list after  reversal*/
               phead->pnext=ReverseKNodesAtATime(nextstart,k);

return newHead;
}
else
{
return phead;
}
}

//
// Finds and returns kth element from end of list if exist else returns NULL
//
PNODE LastKthNode(PNODE phead,int k)
{
PNODE back=phead,
  front=phead;

if(k<1)
return NULL;
else
{
// move front forward till number of nodes between 
                // front and back becomes not equal to k-1
while(front && k--)
{
front=front->pnext;
}

if(k!=-1)
{
if(!front)
printf("Error\n");
else
return NULL;
}
else
{
// when front becomes null, our back points to last kth  
                        // nodes because initial difference of k-1 nodes
while(front)
{
front=front->pnext;
back=back->pnext;
}
return back;
}
}
}

int main(void)
{
PNODE phead=NULL;
DATA d;
int i;
        //insert 10 elements 
for(i=1;i<=10;i++)
{
d.key=i;
phead=InsertAtStart(phead,d);
}
phead=Reverse(phead);
printf("List Reversed\n");
Traverse(phead);
printf("Reversed 2 at a time\n");
phead=ReverseKNodesAtATime(phead,2);
Traverse(phead);
PNODE pLastkthNode=LastKthNode(phead,6);
if(pLastkthNode)
{
printf("Last 6th node: %d\n",pLastkthNode->item.key);
}
else
{
printf("Last 6th node doesn't exist\n");
}

        DeleteList(phead);

        return 0;
}

PNODE Reverse(PNODE phead)
{
PNODE ptail,pmiddle;
ptail=pmiddle=NULL;

while(phead)
{
ptail=pmiddle;
pmiddle=phead;
phead=phead->pnext;
pmiddle->pnext=ptail;
}
return pmiddle;
}

PNODE NewNode(DATA item)
{
PNODE pnode=(PNODE)malloc(sizeof(NODE));
if(pnode)
{
pnode->item=item;
pnode->pnext=NULL;
}
return pnode;
}

PNODE InsertAtStart(PNODE phead,DATA item)
{
if(!phead)
{
PNODE pnode=NewNode(item);
if(!pnode)
printf("Failed to allocate memory\n");
return pnode;
}
else
{
PNODE pnewNode=NewNode(item);
if(pnewNode)
pnewNode->pnext=phead;
else
printf("Failed to allocate memory\n");
}
}

PNODE DeleteAtStart(PNODE phead,PDATA pdata)
{
if(!phead)
return phead;
else
{
PNODE pnext=phead->pnext;
*pdata=phead->item;
free(phead);
return pnext;
}
}

void Traverse(PNODE phead)
{
while(phead)
{
printf("%d\n",phead->item.key);
phead=phead->pnext;
}
}

void DeleteList(PNODE phead)
{
while(phead)
{
PNODE ptemp=phead;
phead=phead->pnext;
free(ptemp);
}
}

Please ask for doubt if any. Thank you.

Traversal (inorder,preorder,postorder) of Binary Tree using recursion and also iteratively in c.

Hi friends,
      I will focus on how to traverse binary tree using iterative method which is tricky as compared to traversal using recursion. Consider following binary tree for example:

Inorder traversal means (left,visit,right) for every node starting from root .Inorder traversal for above tree gives:               1 3 4 6 7 8 10 13 14

Preorder traversal means (visit,left,right) for every node starting from root .Preorder traversal for above tree gives:               8 3 1 6 4 7 10 14 13

Postorder traversal means (left,right,visit) for every node starting from root .Postorder traversal for above tree gives:               1 4 7 6 3 13 14 10 8

Assume Node defination as:

typedef struct BinaryTreeNode
{
    int key;
    struct BinaryTreeNode *left,*right,*parent;
}TreeNode;

/*Recursive Inorder traversal: This traversal print keys in non-decreasing sorted order */

void traverse_inorder_rec(TreeNode *root)
{
    if(root!=NULL)
    {
        traverse_inorder_rec(root->left);
        printf("%d ",root->key);
        traverse_inorder_rec(root->right);
    }
}

/*Recursive Preorder traversal*/

void traverse_preorder_rec(TreeNode *root)
{
    if(root!=NULL)
    {
        printf("%d ",root->key);
        traverse_preorder_rec(root->left);
        traverse_preorder_rec(root->right);
    }
}

/*Recursive Postorder traversal: This traversal is helpful for deleting tree*/

void traverse_postorder_rec(TreeNode *root)
{
    if(root!=NULL)
    {
        traverse_postorder_rec(root->left);
        traverse_postorder_rec(root->right);
        printf("%d ",root->key);
    }
}

/*In all 3 iterative traversals we use stack as auxiliary data structure*/

/*Iterative Preorder: This is the most easiest among all 3 iterative traversals*/

void traverse_preorder_iterative(TreeNode *root)
{
    /*
    *Node's currently on stack are nodes whose keys are to be printed
    and left and right both child to be processed later.

    *All TreeNode * in stack are non NULL
    */
    stack<TreeNode *> s;
    if(root!=NULL)
    {
        s.push(root);
        while(!s.empty())
        {
            TreeNode *ptr=s.top();
            s.pop();
            printf("%d ",ptr->key);
            if(ptr->right!=NULL)
                s.push(ptr->right);
            if(ptr->left!=NULL)
                s.push(ptr->left);
        }
    }
}

/*Iterative Inorder traversal*/

void traverse_inorder_iterative(TreeNode *root)
{
        stack<TreeNode *> s;
        TreeNode *current=root;
        bool done =false;
        while(!done)
        {
            if(current)
            {
                s.push(current);
                current=current->left;
            }
            else
            {
                if(s.empty())
                {
                    done=true;
                }
                else
                {
                    current=s.top();
                    s.pop();
                    cout<<current->key<<" ";
                    current=current->right;
                }
            }
        }
}

/*Iterative post order traversal: This is the most trickiest among all this 3 iterative versions.Here we use prevNode pointer for keeping track in which direction we are moving.For eg. Either (upward from left or right ) or (downward from left or right )*/

void traverse_postorder_iterative(TreeNode *root)
{
    if(root!=NULL)
    {
        stack<TreeNode *> s;
        TreeNode *prevNode,*currentNode;
        prevNode=NULL;
        s.push(root);

        while(!s.empty())
        {
            currentNode=s.top();
            if(prevNode==NULL || prevNode->left==currentNode ||                            
                prevNode->right==currentNode)
            {
                if(currentNode->left!=NULL)
                    s.push(currentNode->left);
                else if(currentNode->right!=NULL)
                    s.push(currentNode->right);
                else
                {
                    printf("%d ",currentNode->key);
                    s.pop();
                }
            }
            else if(prevNode==currentNode->left)
            {
                if(currentNode->right!=NULL)
                    s.push(currentNode->right);
                else
                {
                    printf("%d ",currentNode->key);
                    s.pop();
                }
            }
            else if(prevNode==currentNode->right)
            {
                printf("%d ",currentNode->key);
                s.pop();
            }
            prevNode=currentNode;
        }
    }
}

Please comment if any doubt and like if helpful.

For detail explanation of postorder iterative version ,refer to link:http://leetcode.com/2010/10/binary-tree-post-order-traversal.html

Creating pascal triangle using 1-Dimensional array for finding coefficients of (1+x)^n efficiently.

Hi friends,
     As you all know pascal triangle looks like
                                                                     1                                      n=0
                                                                 1      1                                  n=1
                                                             1      2      1                              n=2
                                                          1     3       3      1                         n=3
                                                       1     4     6      4      1                      n=4
                                                    1     5    10   10     5     1                   n=5
                                                 ............................................                so on
Observe some facts:
1)Number of element in ith row = (i+1)

2) ith element in nth row = sum of (i-1)th & (i)th element in (n-1)th row  for 1<i<(n+1)

3)Also ,
For n=0:     (1+x)^0=1
For n=1:     (1+x)^1=1 + 1*(x)
For n=2:     (1+x)^2=1 + 2*(x) + 1*(x*x)
For n=3:     (1+x)^3=1 + 3*(x) + 3*(x*x) + 1*(x*x*x)

Observe the coefficients underlined, they belongs to each row of above triangle. For eg. when n=2,
coefficients are (1,2,1) which is row number 2 of pascal triangle. Similar situation occurs for n=3,here
coefficients are (1,3,3,1) which is row number 3 of pascal triangle.

4)Coefficients of (1+x)^n form sequence :      (nC0,nC1,nC2,.....nCn)    
where nCr=(n!)/(r! * (n-r)!)

So,by finding nth row of pascal triangle we are finding coefficients of (1+x)^n and hence indirectly above sequence of combinations.

Now we will see how to generate above pascal triangle recursively for specified value of 'n' using 1-D array in c++.

Size of 1-D array for above triangle for some n = 1+2+3+....+(n+1) =
 ((n+1)*(n+2))/2

Starting index in this 1-D array for nth row of  pascal triangle= 1+2+...n =
(n*(n+1))/2

//Actual c++ routine starts here:

void Form_Pascal_Triangle(unsigned long int a[],unsigned long int n)
{
    if(n==0)
    {
        a[0]=1;
    }
    else
    {
        Form_Pascal_Triangle(a,n-1);

        unsigned long int PREVTO_NTH_ROW_START_INDEX=(n*(n-1))/2;

        unsigned long int CURRENT_NTH_ROW_START_INDEX=(n*(n+1))/2;

        //initialise first and last element of nth row of pascal triangle
        a[CURRENT_NTH_ROW_START_INDEX]=1;
        a[CURRENT_NTH_ROW_START_INDEX+n]=1;

        for(unsigned long int i=1;i<n;i++)
        {
             a[CURRENT_NTH_ROW_START_INDEX+i] =
                                       a[PREVTO_NTH_ROW_START_INDEX+i-1] +
                                       a[PREVTO_NTH_ROW_START_INDEX+i];
        }
    }
}


int main()
{
    unsigned long int n;
    cout<<"Enter n:";
    cin>>n;
    unsigned long int size=((n*(n+1))/2)+(n+1);
    unsigned long int a[size];
 
    Form_Pascal_Triangle(a,n);

    return 0;
}

Please comment if any doubt and like if helpful.Thanks