Check if Array elements are consecutive

Given an unsorted array of numbers, write a function that returns true if array consists of consecutive numbers. 
Examples:
a) If array is {5, 2, 3, 1, 4}, then the function should return true because the array has consecutive numbers from 1 to 5.
b) If array is {83, 78, 80, 81, 79, 82}, then the function should return true because the array has consecutive numbers from 78 to 83.
c) If the array is {34, 23, 52, 12, 3 }, then the function should return false because the elements are not consecutive.
d) If the array is {7, 6, 5, 5, 3, 4}, then the function should return false because 5 and 5 are not consecutive.
http://algorithms.tutorialhorizon.com/check-if-array-is-consecutive-integers/
http://www.geeksforgeeks.org/check-if-array-elements-are-consecutive/

Approach:
Method 1:Visited Array

The idea is to check for following two conditions. If following two conditions are true, then return true.
1) max – min + 1 = n where max is the maximum element in array, min is minimum element in array and n is the number of elements in array.
2) All elements are distinct.

To check if all elements are distinct, we can create a visited[] array of size n. 

We can map the ith element of input array arr[] to visited array by using arr[i] – min 

as index in visited[].

Method 2:Mark Negative

 This method is O(n) time complexity and O(1) extra space, but it changes the original 

array and it works only if all numbers are positive. We can get the original array by 

adding an extra step though. It is an extension of method 2 and it has the same two steps.

1) max – min + 1 = n where max is the maximum element in array, min is minimum element 

in array and n is the number of elements in array.
2) All elements are distinct.

In this method, the implementation of step 2 differs from method 2. Instead of creating a 

new array, we modify the input array arr[] to keep track of visited elements. 

The idea is to traverse the array and for each index i (where 0 <= i < n), 

make arr[arr[i] – min]] as a negative value. If we see a negative value again then there 

is repetition. 

Merge k sorted arrays

http://www.geeksforgeeks.org/merge-k-sorted-arrays/

http://algorithms.tutorialhorizon.com/merge-k-sorted-arrays/

http://www.programcreek.com/2014/05/merge-k-sorted-arrays-in-java/
http://www.programcreek.com/2013/02/leetcode-merge-k-sorted-lists-java/

Remove Duplicate nodes in BST/BT

Write A Program to Remove Duplicates from BST.

Strategy:

Assuming if duplicate is there in inserting in a BST we put that in the left.
So 2 cases are there :
1.duplicate is the left child of its replica.
2.duplicate is at the successor position of the node.

Pseudo Code:

func(Node *node)
  {
    if(!node)
    return;

if(isduplicateexist(node))
   {
    dupparent=find_dup_parent(node);
    if(dupparent ! =node)
      {
       dup=dupparent->right;
      dupparent->right=dupparent->right->left;
      }
  else
   {
    dup=node->left;
    node->left=node->left->left;
   }

del (dup);
}
func(node->left);
func(node->right);
}

Remove Duplicates from BT.
http://www.mycareerstack.com/question/155/

Median in stream of integers

Given that integers are read from a data stream. Find median of elements read so for in efficient way. For simplicity assume there are no duplicates. For example, let us consider the stream 5, 15, 1, 3 …

After reading 1st element of stream - 5 -> median - 5
After reading 2nd element of stream - 5, 15 -> median - 10
After reading 3rd element of stream - 5, 15, 1 -> median - 5
After reading 4th element of stream - 5, 15, 1, 3 -> median - 4, so on...

Making it clear, when the input size is odd, we take the middle element of sorted data. If the input size is even, we pick average of middle two elements in sorted stream.

Note that output is effective median of integers read from the stream so far. Such an algorithm is called online algorithm. Any algorithm that can guarantee output of i-elements after processing i-th element, is said to be online algorithm. Let us discuss three solutions for the above problem.

http://www.programcreek.com/2015/01/leetcode-find-median-from-data-stream-java/

We will insert the received numbers into such a data structure that we’ll be able to find the median very efficiently. Let’s analyse the possible options.

Method 1:Array Based Solution:

We can insert the integers to an unsorted array, so we’ll just append the numbers to the array one by one as we receive. Insertion complexity is O(1) but finding the median will take O(N) time, if we use the Median of Medians algorithm that I described in my previous post. However, our goal is to find the median most efficiently, we don’t care that much about insertion performance. But this algorithm does the exact opposite, so unsorted array is not a feasible solution.

What about using a sorted array? We can find the position to insert the received number in O(logN) time using binary search. And at any time if we’re asked for the median we can just return the middle element if the array length is odd, or the average of middle elements if the length is even. This can be done in O(1) time, which is exactly what we’re looking for. But there’s a major drawback of using a sorted array. To keep the array sorted after inserting an element, we may need to shift the elements to the right, which will take O(N) time. So, even if finding the position to insert the number takes O(logN) time, the overall insertion complexity is O(N) due to shifting. But finding the median is still extremely efficient, constant time. However, linear time insertion is pretty inefficient and we would prefer a better performance.

Insertion Sort

If we can sort the data as it appears, we can easily locate median element. Insertion Sort is one such online algorithm that sorts the data appeared so far. At any instance of sorting, say after sorting i-th element, the first i elements of array are sorted. The insertion sort doesn’t depend on future data to sort data input till that point. In other words, insertion sort considers data sorted so far while inserting next element. This is the key part of insertion sort that makes it an online algorithm.

However, insertion sort takes O(n²) time to sort n elements. Perhaps we can use binary search oninsertion sort to find location of next element in O(log n) time. Yet, we can’t do data movement in O(log n) time. No matter how efficient the implementation is, it takes polynomial time in case of insertion sort.

Linked Lists:

Let’s try linked lists. First unsorted linked list. Insertion is O(1), we can insert either to the head or tail but we suffer from the same problem of unsorted array. Finding the median is O(N). What if we keep the linked list sorted? We can find the median in O(1) time if we keep track of the middle elements. Insertion to a particular location is also O(1) in any linked list, so it seems great thus far. But, finding the right location to insert is not O(logN) as in sorted array, it’s instead O(N) because we can’t perform binary search in a linked list even if it is sorted. So, using a sorted linked list doesn’t worth the effort, insertion is O(N) and finding median is O(1), same as the sorted array. In sorted array insertion is linear due to shifting, here it’s linear because we can’t do binary search in a linked list. This is a very fundamental data structure knowledge that we should keep at the top of our heads all the time.

Using a stack or queue wouldn’t help as well. Insertion would be O(1) but finding the median would be O(N), very inefficient.

Method 2: Augmented self balanced binary search tree (AVL, RB, etc…)

What if we use trees? Let’s use a binary search tree with additional information at each node, number of children on the left and right subtrees. We also keep the number of total nodes in the tree. Using this additional information we can find the median in O(logN) time, taking the appropriate branch in the tree based on number of children on the left and right of the current node. However, the insertion complexity is O(N) because a standard binary search tree can degenerate into a linked list if we happen to receive the numbers in sorted order.

So, let’s use a balanced binary search tree to avoid worst case behaviour of standard binary search trees. In a height balanced binary search tree (i.e. AVL tree) the balance factor is the difference between the heights of left and right subtrees. A node with balance factor 0, +1, or -1 is considered to be balanced. However, in our tree the balance factor won’t be height, it is the number of nodes in the left subtree minus the number of nodes in the right subtree. And only the nodes with balance factor of +1 or 0 are considered to be balanced. So, the number of nodes on the left subtree is either equal to or 1 more than the number of nodes on the right subtree, but not less. If we ensure this balance factor on every node in the tree, then the root of the tree is the median, if the number of elements is odd. In the even case, the median is the average of the root and its inorder successor, which is the leftmost descendent of its right subtree. So, complexity of insertion maintaining balance condition is O(logN) and find median operation is O(1) assuming we calculate the inorder successor of the root at every insertion if the number of nodes is even. Insertion and balancing is very similar to AVL trees. Instead of updating the heights, we update the number of nodes information.

Thus,

At every node of BST, maintain number of elements in the subtree rooted at that node. We can use a node as root of simple binary tree, whose left child is self balancing BST with elements less than root and right child is self balancing BST with elements greater than root. The root element always holdseffective median.

If left and right subtrees contain same number of elements, root node holds average of left and right subtree root data. Otherwise, root contains same data as the root of subtree which is having more elements. After processing an incoming element, the left and right subtrees (BST) are differed utmost by 1.

Self balancing BST is costly in managing balancing factor of BST. However, they provide sorted data which we don’t need. We need median only. The next method make use of Heaps to trace median.

Method 3:Heaps
Balanced binary search trees seem to be the most optimal solution, insertion is O(logN) and find median is O(1). Can we do better? We can achieve the same complexity with a simpler and more elegant solution. We will use 2 heaps simultaneously, a max-heap and a min-heap with 2 requirements. The first requirement is that the max-heap contains the smallest half of the numbers and min-heap contains the largest half. So, the numbers in max-heap are always less than or equal to the numbers in min-heap. Let’s call this the order requirement. The second requirement is that, the number of elements in max-heap is either equal to or 1 more than the number of elements in the min-heap. So, if we received 2N elements (even) up to now, max-heap and min-heap will both contain N elements. Otherwise, if we have received 2N+1 elements (odd), max-heap will contain N+1 and min-heap N. Let’s call this the size requirement.

The heaps are constructed considering the two requirements above. Then once we’re asked for the median, if the total number of received elements is odd, the median is the root of the max-heap. If it’s even, then the median is the average of the roots of the max-heap and min-heap. Let’s now analyse why this approach works, and how we construct the heaps.

We will have two methods, insert a new received number to the heaps and find median. The insertion procedure takes the two requirements into account, and it’s executed every time we receive a new element. We take two different approaches depending on whether the total number of elements is even or odd before insertion.

Let’s first analyze the size requirement during insertion. In both cases we insert the new element to the max-heap, but perform different actions afterwards. In the first case, if the total number of elements in the heaps is even before insertion, then there are N elements both in max-heap and min-heap because of the size requirement. After inserting the new element to the max-heap, it contains N+1 elements but this doesn’t violate the size requirement. Max-heap can contain 1 more element than min-heap. In the second case, if the number of elements is odd before insertion, then there are N+1 elements in max-heap and N in min-heap. After we insert the new element to the max-heap, it contains N+2 elements. But this violates the size constraint, max-heap can contain at most 1 more element than min-heap. So we pop an element from max-heap and push it to min-heap. The details will be described soon.

Now let’s analyse the order requirement. This requirement forces every element in the max-heap to be less than or equal to all the elements in min-heap. So the max-heap contains the smaller half of the numbers and the min-heap contains the larger half. Note that by design the root of the max-heap is the maximum of the lower half, and root of the min-heap is the minimum of the upper half. Keeping these in mind, we again take two different actions depending on whether the total number of elements is even or odd before insertion. In the even case we just inserted the new element to the max-heap. If the new element is less than all the elements in the min-heap, then the order constraint is satisfied and we’re done. We can perform this check by comparing the new element to the root of the min-heap in O(1) time since the root of the min-heap is the minimum. But if the new element is larger than the root of min-heap then we should exchange those elements to satisfy the order requirement. Note that in this case the root of the max-heap is the new element. So we pop the the root of min-heap and insert it to max-heap. Also pop the root of max-heap and insert it to min-heap. In second case, where the total number of elements before insertion is odd, we inserted the new element to max-heap, then we popped an element and pushed it to the min-heap. To satisfy the order constraint, we pop the maximum element of the max-heap, the root, and insert it to the min-heap. Insertion complexity is O(logN), which is the insertion complexity of a heap.

That is exactly how the insertion procedure works. We ensured that both size and order requirements are satisfied during insertion. Find median function works as follows. At any time we will be queried for the median element. If the total number of elements at that time is odd, then the median is the root of the max-heap. Let’s visualize this with an example. Assume that we have received 7 elements up to now, so the median is the 4th number in sorted order. Currently, max-heap contains 4 smallest elements and min-heap contains 3 largest because of the requirements described above. And since the root of the max-heap is the maximum of the smallest four elements, it’s the 4th element in sorted order, which is the median. Else if the total number of elements is even, then the median is the average of the roots of max-heap and min-heap. Let’s say we have 8 elements, so the median is the average of 4th and 5th elements in sorted order. Currently, both the max-heap and min-heap contain 4 numbers. Root of the max-heap is the maximum of the smallest numbers, which is 4th in sorted order. And root of the min-heap is the minimum of the largest numbers, which is 5th in sorted order. So, the median is the average of the roots. In both cases we can find the median in O(1) time because we only access the roots of the heaps, neither insertion nor removal is performed. Therefore, overall this solution provides O(1) find heap and O(logN) insert.

A code is worth a thousand words, here is the code of the 2-heaps solution. As you can see, it’s much less complicated than it’s described. We can use the heapq module in python, which provides an implementation of min-heap only. But we need a max-heap as well, so we can make a min-heap behave like a max-heap by multiplying the number to be inserted by -1 and then inserting. So, every time we insert or access an element from the max-heap, we multiply the value by -1 to get the original number:

class streamMedian:
    def __init__(self):
        self.minHeap, self.maxHeap = [], []
        self.N=0

    def insert(self, num):
        if self.N%2==0:
            heapq.heappush(self.maxHeap, -1*num)
            self.N+=1
            if len(self.minHeap)==0:
                return
            if -1*self.maxHeap[0]>self.minHeap[0]:
                toMin=-1*heapq.heappop(self.maxHeap)
                toMax=heapq.heappop(self.minHeap)
                heapq.heappush(self.maxHeap, -1*toMax)
                heapq.heappush(self.minHeap, toMin)
        else:
            toMin=-1*heapq.heappushpop(self.maxHeap, -1*num)
            heapq.heappush(self.minHeap, toMin)
            self.N+=1

    def getMedian(self):
        if self.N%2==0:
            return (-1*self.maxHeap[0]+self.minHeap[0])/2.0
        else:
            return -1*self.maxHeap[0]

Useful Links:

http://www.geeksforgeeks.org/archives/14873
http://www.ardendertat.com/2011/11/03/programming-interview-questions-13-median-of-integer-stream/

Example 2:
How to find the sorted median of a continuous stream of integers. let the stream is 0,1,2,3,4 the median is 2. now let -2 comes and the median for stream -2,0,1,2,3,4 still the median is 2 or it can be 1. now again -4 comes the median for the stream -4,-2,0,1,2,3,4 is 1. 

Pending

IdenticalTree(), mirrorTree(), isFoldableTree() and isSumTree()

Same Tree:

Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way

http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/
http://www.geeksforgeeks.org/iterative-function-check-two-trees-identical/

int sameTree(struct node* a, struct node* b) { 

int sameTree(struct tree* a, struct tree* b)
{

    if (a==NULL && b==NULL)
        return 1;
    else if (a!=NULL && b!=NULL)
   {
        return
        (
            a->data == b->data &&
           sameTree(a->left, b->left) &&
           sameTree(a->right, b->right)
        );
    }
    else return 0;
}
Time Complexity:
Complexity of the identicalTree() will be according to the tree with lesser number of nodes. Let number of nodes in two trees be m and n then complexity of sameTree() is O(m) where m < n.

Iterative solution:

If they are binary search trees then you can do any kind of traversal such as inorder, preorder etc, in case of a general tree we can do a breadth first traversal from left most to right most child of a node and if that is same then the two trees are identical.

Mirror Tree
Change a tree so that the roles of the left and right pointers are swapped at every node.
So the tree...
       4
      / \
     2   5
    / \
   1   3

 is changed to...
       4
      / \
     5   2
        / \
       3   1

void mirror(struct tree* root)

{

  if (root==NULL)

    return;

  else

  {

    struct node* temp;

    mirror(root->left);

    mirror(root->right);

    temp        = root->left;

    root->left  = root->right;

    root->right = temp;

  }

}

Time Complexity:O(n)
Auxiliary Space : If we don’t consider size of stack for function calls then O(1) otherwise O(n).

Fold-able Tree:

Given a binary tree,find whether it can be foldable or not :

A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.

Method 1:Without Mirroring
There are mainly two functions:
// Checks if tree can be folded or not

IsFoldable(root)
1) If tree is empty then return true
2) Else check if left and right subtrees are structure wise mirrors of
    each other. Use utility function IsFoldableUtil(root->left,
    root->right) for this.

// Checks if n1 and n2 are mirror of each other.

IsFoldableUtil(n1, n2)
1) If both trees are empty then return true.
2) If one of them is empty and other is not then return false.
3) Return true if following conditions are met
   a) n1->left is mirror of n2->right
   b) n1->right is mirror of n2->left




Code:

bool IsFoldable(struct node *root)

{

     if (root == NULL)

     {  return true;  }

     return IsFoldableUtil(root->left, root->right);

}

bool IsFoldableUtil(struct node *n1, struct node *n2)

{

    if (n1 == NULL && n2 == NULL)

    {  return true;  }

    if (n1 == NULL || n2 == NULL)

    {  return false; }

    return IsFoldableUtil(n1->left, n2->right) &&

           IsFoldableUtil(n1->right, n2->left);

}

Method 2:Mirroring Tree

1) If tree is empty, then return true.
2) Convert the left subtree to its mirror image
    mirror(root->left);
3) Check if the structure of left subtree and right subtree is same
   and store the result.
    res = isStructSame(root->left, root->right); /*isStructSame()
        recursively compares structures of two subtrees and returns
        true if structures are same */
4) Revert the changes made in step (2) to get the original tree.
    mirror(root->left);
5) Return result res stored in step 2.

Code:

bool isFoldable(struct node *root)

{

  bool res;

  if(root == NULL)

    return true;

  mirror(root->left);

  res = isStructSame(root->left, root->right);

  mirror(root->left);

  return res;

}

bool isStructSame(struct node *a, struct node *b)

{

  if (a == NULL && b == NULL)

  {  return true; }

  if ( a != NULL && b != NULL &&

       isStructSame(a->left, b->left) &&

       isStructSame(a->right, b->right)

     )

  {  return true; }

  return false;

}

void mirror(struct node* node)

{

  if (node==NULL)

    return;

  else

  {

    struct node* temp;

    mirror(node->left);

    mirror(node->right);

    temp        = node->left;

    node->left  = node->right;

    node->right = temp;

  }

}

Time complexity: O(n)

Sum Tree:
http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/
http://www.geeksforgeeks.org/convert-a-given-tree-to-sum-tree/
http://www.geeksforgeeks.org/check-for-children-sum-property-in-a-binary-tree/
http://www.geeksforgeeks.org/convert-an-arbitrary-binary-tree-to-a-tree-that-holds-children-sum-property/
http://www.geeksforgeeks.org/transform-bst-sum-tree/

Double Tree:
For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree.
So the tree...
    2
   / \
  1   3

 is changed to...
       2
      / \
     2   3
    /   /
   1   3
  /
 1
Concept:
Recursively convert the tree to double tree in postorder fashion. For each node, first convert the left subtree of the node, then right subtree, finally create a duplicate node of the node and fix the left child of the node and left child of left child.
Code:

void doubleTree(struct node* node)

{

  struct node* oldLeft;

  if (node==NULL) return;

  doubleTree(node->left);

  doubleTree(node->right);

  oldLeft = node->left;

  node->left = newNode(node->data);

  node->left->left = oldLeft;

}
Time Complexity: O(n) where n is the number of nodes in the tree.

Binary heap

http://quiz.geeksforgeeks.org/binary-heap/
http://quiz.geeksforgeeks.org/heap-sort/
http://www.geeksforgeeks.org/applications-of-heap-data-structure/
http://www.geeksforgeeks.org/heap/
http://www.geeksforgeeks.org/why-is-binary-heap-preferred-over-bst-for-priority-queue/
http://www.geeksforgeeks.org/g-fact-85/

Check if a given Binary Tree is Heap
Given a binary tree we need to check it has heap property or not, Binary tree need to fulfill following two conditions for being a heap –
It should be a complete tree (i.e. all levels except last should be full).
Every node’s value should be greater than or equal to its child node (considering max-heap).

http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-heap/

Check if a given array represents a Binary Heap
http://www.geeksforgeeks.org/how-to-check-if-a-given-array-represents-a-binary-heap/

Convert min Heap to max Heap
http://www.geeksforgeeks.org/convert-min-heap-to-max-heap/

Heap Operations

1.Heapify
2 Insertion
3.Deletion
4.Heapsort

1. Building a heap:
Lets take an array with the following elements:
4  1  3  2  16  9  10  14  8  7
Note:-------------------------
Parent( i ) return ⌊i/2⌋
Left( i ) return 2i
Right( i ) return 2i + 1

Build-Max-Heap (A) 1 A.heap-size ← A.length /*@ loop-invariant \forall int j;             i < j ≤ A.length;            A[ j ] ≥ A[Left( j )] &&                       A[ j ] ≥ A[Right( j )] @*/  2 for i ← ⌊ A.length/2 ⌋ downto 1 do 3    Max-Heapify (A, i)

Max-Heapify (A, i) 1 l ← Left (i) 2 r ← Right (i) 3 if l ≤ A.heap-size and A[l] > A[i] 4    then largest ← l 5    else largest ← i 6 if r ≤ A.heap-size and A[r] > A[largest] 7    then largest ← r 8 if largest ≠ i then 9    exchange A[i] ↔ A[largest] 10    Max-Heapify (A, largest)

A.length = 10
i starts at 5, the last parent in the array: always at  ⌊ n/2 ⌋
Max-Heapify is applied to subtrees rooted at nodes (in order): 16, 2, 3, 1, 4.
Note that Max-Heapify is run on each node that is a parent:starts with the last parent in the array: always at  ⌊n/2⌋

Note:Max-Heapify(A, largest) is called as after swapping the new largest may not be heapified
e.g. After swapping 16 and 1 1 becomes new largest and 7 is greater than 1 in that tree.So heapify needs to be called on 1 to take 7 into its proper position.
Visualisation:

• The number of times through the loop is  ⌊n/2⌋  or O(n)
  
• Max-Heapify T(n) = Θ(lg n)
  
• Build-Max-Heap T(n) = O(n lg n)

Useful Link:
http://homepages.ius.edu/rwisman/C455/html/notes/Chapter6/BldHeap.htm

Insert a node into a heap:
To add an element to a heap we must perform an up-heap operation (also known as bubble-up, percolate-up, sift-up, trickle up, heapify-up, or cascade-up), by following this algorithm:

1. Add the element to the bottom level of the heap or to the end of the array.
2. Compare the added element with its parent; if they are in the correct order, stop.
3. If not, swap the element with its parent and return to the previous step.

Suppose we have a heap as follows

Let's suppose we want to add a node with key 15 to the heap. First, we add the node to the tree at the next spot available at the lowest level of the tree. This is to ensure that the tree remains complete.

Let's suppose we want to add a node with key 15 to the heap. First, we add the node to the tree at the next spot available at the lowest level of the tree. This is to ensure that the tree remains complete.

Now we do the same thing again, comparing the new node to its parent. Since 14 < 15, we have to do another swap:

Now we are done, because 15   20.


Useful Link:
http://en.wikipedia.org/wiki/Binary_heap
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm
3.Heap Sort:
The heap sort combines the best of both merge sort and insertion sort. Like merge sort, the worst case time of heap sort is O(n log n) and like insertion sort, heap sort sorts in-place. The heap sort algorithm starts by using procedure BUILD-HEAP to build a heap on the input array A[1 . . n]. Since the maximum element of the array stored at the root A[1], it can be put into its correct final position by exchanging it with A[n] (the last element in A). If we now discard node n from the heap than the remaining elements can be made into heap. Note that the new element at the root may violate the heap property. All that is needed to restore the heap property.

HEAPSORT (A)

1. BUILD_HEAP (A)
2. for i ← length (A) down to 2 do
   exchange A[1] ↔ A[i]
   heap-size [A] ← heap-size [A] - 1
   Heapify (A, 1)

Code:

void heapSort(int numbers[], int array_size)
{
  int i, temp;

  for (i = (array_size / 2)-1; i >= 0; i--)
    siftDown(numbers, i, array_size);

  for (i = array_size-1; i >= 1; i--)
  {
    temp = numbers[0];
    numbers[0] = numbers[i];
    numbers[i] = temp;
    siftDown(numbers, 0, i-1);
  }
}


void siftDown(int numbers[], int root, int bottom)
{
  int done, maxChild, temp;

  done = 0;
  while ((root*2 <= bottom) && (!done))
  {
    if (root*2 == bottom)
      maxChild = root * 2;
    else if (numbers[root * 2] > numbers[root * 2 + 1])
      maxChild = root * 2;
    else
      maxChild = root * 2 + 1;

    if (numbers[root] < numbers[maxChild])
    {
      temp = numbers[root];
      numbers[root] = numbers[maxChild];
      numbers[maxChild] = temp;
      root = maxChild;
    }
    else
      done = 1;
  }
}

Useful Link:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm
http://www.algorithmist.com/index.php/Heap_sort.c

Deletion in a heap:[ Follows the same sift_down method as in heapsort
The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) and restoring the properties is called down-heap (also known as bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down and extract-min/max).

1. Replace the root of the heap with the last element on the last level.
2. Compare the new root with its children; if they are in the correct order, stop.
3. If not, swap the element with one of its children and return to the previous step. (Swap with its smaller child in a min-heap and its larger child in a max-heap.)

Useful Link:
http://en.wikipedia.org/wiki/Binary_heap
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

Search an Item in a sorted array with shifted elements

Question 1:
You are given a sorted array with shifted elements. Elements can be shifted to the left or right by 'i' number of places. The sign of 'i' denotes the direction of the shift. For positive 'i' direction of shift is right and left for negative 'i'.

For example, consider the sorted array 2, 3, 4, 8, 10, 11. A shift of 3 places to the right would be denoted by i=2 and the shifted array would look like this: 10, 11, 2, 3, 4, 8,
For i=-2, the shifted array would look like: 4, 8, 10, 11, 2, 3.Search an item 10 in the array.

http://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/
Question 2:
Find the minimum element in a sorted and rotated array
http://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/

Question 3:
Alternatively, Given an array of unsigned integers which is initially increasing and then decreasing find the maximum value in the array
http://www.geeksforgeeks.org/find-the-maximum-element-in-an-array-which-is-first-increasing-and-then-decreasing/

Question 4:
Given a sorted and rotated array, find if there is a pair with a given sum
Given an array that is sorted and then rotated around an unknown point. Find if array has a pair with given sum ‘x’. It may be assumed that all elements in array are distinct.

http://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/


Method 1:Binary Search [ Finding point of rotation ]
Find the pivot point, divide the array in two sub-arrays and call binary search.
The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only only element for which next element to it is smaller than it.
OR
1)   Assuming that it is an increasing order sorted array that has been rotated, except for one index A[i] < A[i+1] always holds.

2)   When we pick the middle element, of a such an array, out of the two sub-arrays one will always be in a strictly increasing order.

3)   The point of rotation, would then simply lie in the second sub-array which is not strictly increasing. 

By the virtue of the above mentioned points, whenever we examine the two halves, the starting element will always lie in that half which is not in strictly increasing order. Now once we have decide how to go about doing the binary search, we need to decide what we have to search. We are not directly searching for an number here, but an index i such that A[i] > A[i+1], since this is not possible in a normal sorted array, the index 'i+1' is the pivot of rotation and A[i+1] is the smallest number in the array.

int pivotedBinarySearch(int arr[], int arr_size, int no)
{
   int pivot = findPivot(arr, 0, arr_size-1);
   if(arr[pivot] == no)
     return pivot;
   if(arr[0] <= no)
     return binarySearch(arr, 0, pivot-1, no);
   else
     return binarySearch(arr, pivot+1, arr_size-1, no);
}    


int findPivot(int arr[], int low, int high)
{
   int mid = (low + high)/2;  
   if(arr[mid] > arr[mid + 1])
     return mid;
   if(arr[low] > arr[mid])
     return findPivot(arr, low, mid-1);
   else
     return findPivot(arr, mid + 1, high);
}

Note: If point of rotation is given then we can directly continue with binary search keeping in mind the following point:

// Take care of scenarios where the shift is more
   // than the length of the array
   shift = shift % myArray.Length;

   // -ve shift can be seen as positive shift equal to
   // the length of the array - ( -ve shift)
   if (shift < 0)
       shift = myArray.Length + shift;

Alternatively If we will find Pivot without recursion,

int findSmallest(int* a, int length)

{

    if(length==0 || a==NULL)

        return -1;

         

    int start=0,end=length-1;

     

    while(start <= end)

    {

        int mid=(start+end)/2;

         

        // this is the standard comparison condition

        if(a[mid] > a[mid+1])

            return a[mid+1];

         

        // an extra comparison that adds the optimization that

        // if the mid element is the smallest one, there will not be

        // extra iterations

        if(a[mid] < a[mid-1])

            return a[mid];

             

         

        // the left half is in strictly increasing order

        // so we search in the second half

        if(a[mid] > a[start])

        {

            start = mid+1;

        }

        // The array is not rrotated so we simply

        // return the first element of the array

        else if(a[mid] >= a[start] && a[mid] <= a[end])

             return a[0];

          

        // the right half is in strictly increasing order

        // and hence we will search in the left half

         else

           end= mid-1;

         

    }

    return -1;

}

Time:O(logn)

Method 2:Recursive Without Finding Point of rotation

A sorted array, say: {1,2,3,4,5,6,7,8,9,10,11,12}, do right rotate through carry unknown times, and then it might become: {6,7,8,9,10,11,12,1,2,3,4,5}. Now we need get the index of a given number, say 4, from the array within O(log(n)) time.

We can think of it this way: take the middle element of array, if target is found, fine; if not, and then array become two parts, one is sorted array, the other is shifted sorted array. As illustrated as below diagram:



If the target falls into the sorted array half, we can simple do a binary search; otherwise, repeat this operation in the other half in recursive way. You can see this is divide-and-conquer algorithm. Obviously this is O(log(n)).

// // A typical binary search implementation // int _BinarySearch(unsigned int ShiftedArray[], unsigned int start,unsigned int end, unsigned int target) {     // Not found     if( start == end && ShiftedArray[start] != target) {        return -1;     }     unsigned int middle = start + (end - start)/2;     if(target == ShiftedArray[middle])     {        return middle;     } else if (target > ShiftedArray[middle]) {        return _BinarySearch(ShiftedArray, middle + 1, end, target);     } else {        return _BinarySearch(ShiftedArray, start, middle - 1, target);     } } // // Select a given number from shifted array. // ShiftedArray is something like = {6,7,8,9,10,11,12,1,2,3,4,5} // If found, return index of the number; if not, reutrn -1 // Require log(N) // int SearchShiftedArray(unsigned int ShiftedArray[], unsigned int start,unsigned int end, unsigned int target) {     // Start meets end     if( start == end && ShiftedArray[start] != target) {        return -1;     }     unsigned int middle = start + (end - start)/2;     if(target == ShiftedArray[middle])     {        return middle;     }      else if(ShiftedArray[middle] < ShiftedArray[start]) { // Right half is sorted linearly        if((target > ShiftedArray[middle]) && (target <= ShiftedArray[end])) {            return _BinarySearch(ShiftedArray, middle + 1, end, target);        } else {            return SearchShiftedArray(ShiftedArray, start, middle-1, target);        }     } else { // Left half is sorted linearly        if((target >= ShiftedArray[start]) && (target < ShiftedArray[middle])) {            return _BinarySearch(ShiftedArray, start, middle - 1, target);        } else {            return SearchShiftedArray(ShiftedArray, middle + 1, end, target);        }     } }

Test cases

Positive: {6,7,8,9,10,11,12,1,2,3,4,5}, target = 3, target = 8 Negative: {6,7,8,9,10,11,12,1,2,3,4,5}, target = 0, target = 13 Boundary: {6,7,8,9,10,11,12,1,2,3,4,5}, target = 6, target = 5 Exceptional: {…max}, target = max

Method 2.2:Iterative without Pivot--Best Method

First, we know that it is a sorted array that’s been rotated. Although we do not know where the rotation pivot is, there is a property we can take advantage of. Here, we make an observation that a rotated array can be classified as two sub-array that is sorted (i.e., 4 5 6 7 0 1 2 consists of two sub-arrays 4 5 6 7 and 0 1 2.

Do not jump to conclusion that we need to first find the location of the pivot and then do binary search on both sub-arrays. Although this can be done in O(lg n) time, this is not necessary and is more complicated.

In fact, we don’t need to know where the pivot is. Look at the middle element (7). Compare it with the left most (4) and right most element (2). The left most element (4) is less than (7). This gives us valuable information — All elements in the bottom half must be in strictly increasing order. Therefore, if the key we are looking for is between 4 and 7, we eliminate the upper half; if not, we eliminate the bottom half.

When left index is greater than right index, we have to stop searching as the key we are finding is not in the array.

Since we reduce the search space by half each time, the complexity must be in the order of O(lg n). It is similar to binary search but is somehow modified for this problem. In fact, this is more general than binary search, as it works for both rotated and non-rotated arrays.

int rotated_binary_search(int A[], int N, int key) {

  int L = 0;

  int R = N - 1;

  while (L <= R) {

    // Avoid overflow, same as M=(L+R)/2

    int M = L + ((R - L) / 2);

    if (A[M] == key) return M;

    // the bottom half is sorted

    if (A[L] <= A[M]) {

      if (A[L] <= key && key < A[M])

        R = M - 1;

      else

        L = M + 1;

    }

    // the upper half is sorted

    else {

      if (A[M] < key && key <= A[R])

        L = M + 1;

      else

        R = M - 1;

    }

  }

  return -1;

}

If we are required to find the rotation point then we can proceed as follows

This problem is in fact the same as finding the minimum element’s index. If the middle element is greater than the right most element, then the pivot must be to the right; if it is not, the pivot must be to the left.

int FindSortedArrayRotation(int A[], int N) {

  int L = 0;

  int R = N - 1;

  while (A[L] > A[R]) {

    int M = L + (R - L) / 2;

    if (A[M] > A[R])

      L = M + 1;

    else

      R = M;

  }

  return L;

}

Useful Link:

http://www.leetcode.com/2010/04/searching-element-in-rotated-array.html

Solution if duplicates are allowed:

#include <iostream>

int rotatedSearch(int values[], int start, int end,int x)
{
    if(values[start] == x){
        return start;
    } else if(values[end] == x){
        return end;
    } else if(end - start == 1) {
        return -1;
    }
    int middle = (start + end) / 2;

    
    if((values[start]==values[middle]) && (values[middle] == values[end]))
        { 
          if((rotatedSearch(values, start, middle, x))!=-1)
              return rotatedSearch(values, start, middle, x);
          else    
               return rotatedSearch(values, middle, end, x);
        }
               
    if(values[start] <= values[middle]){
        if(x <= values[middle] && x >= values[start]){
            return rotatedSearch(values, start, middle, x);
        } else {
            return rotatedSearch(values, middle, end, x);
        }
    } else if(values[middle] <= values[end]){
        if(x >= values[middle] && x <= values[end] ){
            return rotatedSearch(values, middle, end, x);
        } else {
            return rotatedSearch(values, start, middle, x);
        }
    } else {
        return -1;
    }
}

int main()
{
 //  int arr[12] = {1, 2, 2, 3, 4, 5, 6, 7, 1, 1, 1, 1};
   int arr[13] = {1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1};
  //int arr[13] = {1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1};
   printf("Index of the element is %d", rotatedSearch(arr, 0,11, 2)); 
   getchar();
   return 0;
}

Question 2:Modified Binary Search to find maximum element
int search(int* arr, int strt, int end)
{
    int mid = (strt+end)/2;

    if((arr[mid-1] < arr[mid]) &&  (arr[mid] > arr[mid+1]))
        return arr[mid];
    else if(arr[mid-1] < arr[mid])
        return search(arr, mid+1, end);
    else if(arr[mid] > arr[mid+1])
        return search(arr, strt, mid-1);
}

int main()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 6, 5, 4};

    printf("%d\n", search(arr, 0, 9));
    return 0;
}