Bubblesort is a sorting technique which arrange elements in the increasing order by moving across the array and swapping the adjacent elements that are out of order.The complexity of bubble sort is O(n2).

The steps followed are :

  • Move from first to the last element of array.
  • Swap the element if it is greater than adjacent element.
  • No need to swap if adjacent element is greater.


#include <stdio.h>

void bubble(int [], int);

int main()
  int arr[50], n, a, b;
  //printf("Enter number of elements\n");
  scanf("%d", &n);
  //printf("Enter elements of array \n");
  printf("Unsorted list is :\t");
  for (a = 0; a < n; a++)
  scanf("%d", &arr[a]);
  bubble(arr, n);
  printf("\nSorted list is:\t");
  for ( a = 0 ; a < n ; a++ )
     printf("%d\t", arr[a]);
  return 0;

void bubble(int array[], int n)
  int a, b, temp;
  for (a = 0 ; a < ( n - 1 ); a++)
    for (b = 0 ; b < n - a - 1; b++)
      if (array[b] > array[b+1])
      	temp         = array[b];
        array[b]   = array[b+1];
        array[b+1] = temp;

Run Example Consider an  array with elements 3,7,2,10,1,35,15,5,30,4,8.In order to sort elements,iterations are used.In the first iteration when i=1 sorting is done as given in  Fig 1 and Fig 2.Refer to Fig 3 and 4 for second iteration i.e i=2,Fig 5 and 6 for i=3.Fig 7 and 8 for i=4,Fig 9 and 10 for i=5.Fig 11 and 12 for i =6 respectively.

Screen Shot 2014-06-18 at 3.21.24 PM

Fig 1 : i=1

Screen Shot 2014-06-18 at 3.23.04 PM

Fig 2 : i=1

Screen Shot 2014-06-18 at 3.25.55 PM

Fig 3 : i=2

Screen Shot 2014-06-18 at 3.26.57 PM

Fig 4 : i =2

Screen Shot 2014-06-18 at 3.29.25 PM

Fig 5 : i=3

Screen Shot 2014-06-18 at 3.32.47 PM

Fig 6 : i=3

Screen Shot 2014-06-18 at 3.35.19 PM

Fig 7 : i=4

Screen Shot 2014-06-18 at 3.37.45 PM

Fig 8 : i=4

Screen Shot 2014-06-18 at 3.42.22 PM

Fig 9 : i=5

Screen Shot 2014-06-18 at 3.44.58 PM

Fig 10 : i=5

Screen Shot 2014-06-18 at 3.47.25 PM

Fig 11 : i=6

Screen Shot 2014-06-18 at 3.50.03 PM

Fig 12 : i=6


Short URL: http://tinyit.cc/4d00f0
By Cusp2207 on June 18, 2014 | Computer Science | A comment?


Sorting is a technique to arrange the sequence of elements either in ascending or descending order. Quicksort is an efficient way to sort elements of array.The average running time of quicksort is O(nlogn).The steps followed in quicksort are :

  • Choose the pivot element(Say we choose the pivot element in the beginning of array).
  •  Scan from right to left and find first element in list which is less than the pivot element.Stop scanning as soon the element is found.
  • Swap it with the pivot element.
  • Now scan from left to right to find the first element which is greater than pivot element.
  • Swap the element with pivot.
  • Continue the process till the list is sorted or we get a list for which the above process fails to be followed up.
  • Divide/partition  the array with pivot in between into two sub-arrays .
  • Same process is followed on both the sub-arrays separately and further partitioning and processing is done if necessary.
  • Combine all the sub-arrays and their pivot elements to get a sorted array.


void swap (int arr[], int left, int right)
 int temp;
void quicksort( int arr[], int low, int high )
 int pivot;
 if ( high > low )
  pivot = partition( arr, low, high );
  quicksort( arr, low, pivot-1 );
  quicksort( arr, pivot+1, high );
int partition( int arr[], int low, int high )
 int left, right;
 int item_pivot;
 int pivot = left = low; 
 item_pivot = arr[low]; 
 right = high;
 while ( left < right ) 
  while( arr[left] <= item_pivot ) 
  while( arr[right] > item_pivot) 
  if ( left < right ) 
 arr[low] = arr[right];
 arr[right] = item_pivot;
 return right;
void printarray(int arr[], int);
int main()
 int arr[30], i, n;
 //printf("\nEnter no. of elements: "); 
 scanf("%d", &n);
 //printf("\nEnter the elements: \n");
 for (i=0; i<n; i++)
  scanf ("%d", &arr[i]);
 printf("\nUnsorted array: \n");
 printf("\nSorted array: \n");
 void printarray(int arr[], int n)
 int i;
 for (i=0; i<n; i++)
  printf(" %d ", arr[i]);




Say we have an array with elements 7,44,2,10,1,35,74,88,5,3,15.Scanning from right to left is done to to find element less than pivot and from left to right is done to find element greater than pivot.

Figure 1

  • The pivot element is the first element i.e 7.
  • Scan from  right to left and find element less than 7.3 is the first element so it is swapped with the pivot element.
  • Scan from left to right and find element greater than 7.44 is the first element encountered so it swapped with 7.
  • Scan from right to left.5 is less than pivot element i.e. 7 so they are swapped.
  • Scan from left to right.10 >7,so it swapped with 7.
  • Scan right-left.1 <7 so they are swapped.
  • Scan from left to right.There is no element in the list before pivot which is greater than pivot itself.Thus list is divided into two sub-lists S1 and S2 such that elements in S1 are less than pivot and elements in S2 are greater than pivot.
Screen Shot 2014-06-16 at 7.19.46 PM

Fig 1 : Example


Figure 2

  • S1 has 3,5,2,1  with pivot element 3 and S2 has 35 74 88 10 44 15 with pivot element 35.(Fig 2)
  • Scan right to left in S1 and find element less than 3.1 <3 so they are exchanged.
  • Scan left-right in S1 and find element greater than 3.5>3 so they are swapped.
  • Scan right-left in S1.2<3 so they are swapped and sub-list S1 gets sorted.
Screen Shot 2014-06-16 at 7.21.49 PM

Fig 2 : Sublist S1


Figure 3

  • Scan right-left in S2.15<35 ,so they are swapped
  • Left-right -74>35 so they are swapped.
  • Right-left-10<35 so they are swapped.
  • Left-Right – 88 >35 so they are swapped.
Screen Shot 2014-06-16 at 7.23.01 PM

Fig 3 : Sublist S2 


Figure 4

  • Partition the sub-list into two further sub-lists S3 and S4.S3 has 15,10 and S4 has 88,44,74 .
  • Scan right-left in S3.10<15 so they are swapped and scanning from left-right does not gives any result.
  • S3 becomes sorted.
Screen Shot 2014-06-16 at 7.23.41 PM

Fig 4 : Sublist S3

 Figure 5

  • Scan right-left in S4.Pivot is 88.74<88 so they are swapped.
  • Scanning left to right is a failed attempt.
Screen Shot 2014-06-16 at 7.25.58 PM

Fig 5 : Sublist S4

Figure 6

  • Partition S4 into S5 and S6.S5 has 74,44 and S6 is empty.
  • Scan right-left in S5.Pivot is 74.44<74 so they are swapped and list becomes sorted.
Screen Shot 2014-06-16 at 7.25.08 PM

Fig 6 : Sublist S5


Combine sub-lists to obtain a sorted list.

Screen Shot 2014-06-16 at 7.32.19 PM

Fig 7 : Sorted Array


Short URL: http://tinyit.cc/9f8899

Operations on Binomial Heap – Decrease key

Decrease key refers to reducing the key value of any node.If we want to decrease a key in Binomial heap,we will replace the key with reduced value and will repeatedly exchange the reduced key with the parent in order to restore min-heap property.The running time to perform this operation is O(log n).


Say we want to decrease 50 to 4 in binomial heap given in Fig 1.The steps further followed are given in Fig 2,3,4,5 respectively.

Screen Shot 2014-06-11 at 4.40.39 PM

Fig 1 : Binomial heap before decrease-key operation

Screen Shot 2014-06-11 at 4.42.16 PM

Fig 2 : Replace 50 by 4


4 and 21 are swapped in Fig 3 and 4 and  8 are swapped in Fig 4 in order to retain min-heap property.

Screen Shot 2014-06-11 at 4.43.35 PM

Fig 3 : Swap 3 and 21

Screen Shot 2014-06-11 at 4.44.46 PM

Fig 4 : Swap 4 and 8

Screen Shot 2014-06-11 at 4.45.35 PM

Fig 5 : Binomial heap after decrease-key operation


Short URL: http://tinyit.cc/9b8900
By Cusp2207 on June 11, 2014 | Computer Science | 1 comment

Operations on Binomial Heap – Extract-min

In Extract-Min operation node with minimum key is deleted from the binomial heap h.The running time to extract minimum value is  O(log n).The steps followed  are :

  • Find the root (say x) with minimum key.
  • Delete the root.
  • Break the binomial heap into h and h’.
  • Perform the union operation to h and h’.

Given the binomial heap h in Fig 1.The first step is to find the root with minimum key.Node with value 1 is smallest so it is deleted and h is broken down into h and h’(Fig 2).

Screen Shot 2014-06-11 at 2.13.48 PM

Fig 1 : Binomial heap h

Fig 2 : Binomial heaps h and h'

Fig 2 : Binomial heaps h and h’


Perform the union operation on h and h’.

Screen Shot 2014-06-11 at 2.32.37 PM

Fig 3 : Union on h and h’


After the union operation on h and h’ the structure seems like as given in Fig 4

Screen Shot 2014-06-11 at 2.37.11 PM

Fig 4 : Structure after union of h and h’


Different cases are performed according to the situation.x points to 11,next-x points to 2,sibling[next-x] points to 3 as shown in Fig 5

Screen Shot 2014-06-11 at 2.38.52 PM

Fig 5 : Structure after union of h and h’


Case 1 is applied in Fig 6.x now points to 2,next-x points to 3 and sibling[next-x] points to 7.

Screen Shot 2014-06-11 at 2.43.45 PM

Fig 6 : Case 1 applied


Case 3 is applied to Fig 7.Trees with root 2 and 3 are of same order i.e. 1 and 2 is less than 3 so 3 becomes the child of 2.next-x will now point to 7 and sibling[next-x] will point to 4.

Screen Shot 2014-06-11 at 2.48.00 PM

Fig 7 : Case 3 applied



Case 3 is applied again in Fig 8.2 is less than 7 so 7 becomes the child of 2.next-x will now point to 4.

Screen Shot 2014-06-11 at 3.31.52 PM

Fig 8 : Case 3


Case 3 is applied in Fig 9 as 2<4 .So 4 becomes the child of 2.x now points to 2 and next-x points to null.Thus the process stops here.

Screen Shot 2014-06-11 at 3.41.23 PM

Fig 9 : Case 3 applied

Short URL: http://tinyit.cc/29008e

Operations On Binomial Heap – Union

The union of two heaps is the merging root lists by root degree.But if we simply merge two heaps then a problem can arise.There may be a chance that we get two or more trees of same root degree.This violates the property of binomial heap.To deal with this problem we have four cases and solution to these cases respectively. Referring to all figures we choose arbitrary names like :

  • x is the second node of merged heaps.
  • prev-x points to previous node of x.
  • next-x points to next node of x.
  • sibling[next-x] points to next node of next-x.
  • Bk and  B1 are Binomial Heaps of order k and 1 respectively.
  • We apply different cases according to the situation until next-x becomes nil.

Cases in union of binomial heaps

Case 1

If we merge  heaps and have a case like  x points to binomial heap of order k and next-x points to binomial heap of order 1 then ,then we need to shift our pointers towards right.x will now point to binomial heap with order 1.next-k will point to heap with root node d and prev-x will point to heap with root node b and order k.

Screen Shot 2014-06-05 at 4.01.45 PM

Fig 1 : Case 1


Case 2

If in union operation the heaps with root b,c,d are of same order k and x points to heap of order k and root node b,next-x points to next heap of x with same order and root node c and sibling[next-x] points to next heap of next-x again with same order and root node d then pointers shift by one. x now points to heap with root node c,next-x points heap with root d and prev-x points to heap with root b.

Screen Shot 2014-06-05 at 4.36.25 PM

Fig 2 : Case 2


Case 3

After the union operation,if  b,c are of same order and key[x] is less than key[next[x]] then c becomes the left child of b and x remain on pointing to b but next-z now points to points to d which was earlier pointed by sibling[next-x].

Screen Shot 2014-06-10 at 12.43.29 PM

Fig 3 : Case 3


Case 4

The pointer points to same binomial heaps as in case 3 except the difference that key of x is greater than key[next[x]].In this case,b becomes the child of c.c is pointed by x and d is pointed by next-x.

Screen Shot 2014-06-10 at 12.54.47 PM

Fig 4 : Case 4



Consider two heaps h1 and h2 as given in Fig 5.The union operation has to be performed on these two heaps.h1 has binomial trees of order 0,1 and 2.h2 has binomial trees of order 0,1 and 3.At the point of union operation both the heaps are combined together but the resultant structure does not follows heap property i.e the resultant structure has binomial trees of same order.In Fig 5,two trees with root 2 and 5 are of order 0 and two trees with roots 1 and 3 are of order 1 violating the property of heaps.In order to make a structure satisfying heap properties we follow case according to the situation.The union of h1 and h2 is shown in Fig 6.

Screen Shot 2014-06-10 at 4.47.05 PM

Fig 5 : Heaps h1 and h2

Screen Shot 2014-06-11 at 9.54.02 AM

Fig 6 : Union of h1 and h2



In Fig 7,2 is less than 5 and both the trees are of same order i.e 0 so case 3 is followed in which root pointed by next-x(5) becomes the child of x(2) and pointer next-x shifts to right i.e it shifts to 1 and sibling[next-x] also shifts pointer to right i.e to 3.

Screen Shot 2014-06-10 at 5.18.04 PM

Fig 7 : Case 3 applied


In Fig 8,all three binomial trees pointed by x,next-x and sibling[next-x] are of same order i.e 1 so case 2 is followed in which all three pointers shift to right by one i.e x will point to 1,next-x will point to  3 and sibling[next-x] will point to 7.

Screen Shot 2014-06-10 at 5.23.56 PM

Fig 8 : Case 2 applied



In Fig 9,Case 3 is followed as root 1 is less than root 3 and their trees are of same order.Tree with root 3 becomes child of tree with root 1.

Screen Shot 2014-06-10 at 5.31.57 PM

Fig 9 : Case 3 applied


In Fig 10,Case 3 is followed again as root 1 is less than root 7 and their trees are of same order i.e. 2.Tree with root 1 becomes the child of tree with root 7.

Screen Shot 2014-06-10 at 5.40.50 PM

Fig 10 : Case 3 applied


In Fig 11,Case 3 is followed as 1 is less than 4 and their trees are of same order i.e.3.Tree with root 1 becomes the child of tree with root 4. The next-x becomes nil  and so the process of applying cases stop here.We get two binomial trees of different orders.They are of order 1 and 4 respectively.Union of heaps is done satisfying all the properties of binomial heap.

Screen Shot 2014-06-10 at 6.15.30 PM

Fig 11 : Case 3 applied


Short URL: http://tinyit.cc/f799fd

Binomial Heaps

Binomial Heaps are similar to binary heaps with additional feature of implementing binomial series as sequence of trees.The heap(Fig 1) is represented using left child right sibling pointers.It has three links per node (parent,left,right) and the roots of tree are connected using single linked list.The degrees of tree decrease from left to right.

Properties of Binomial Heap

  • Each Binomial tree in the heap obey min-heap property.
  • There can be only 0 or 1 binomial trees for each order .

The root  value of every binomial tree is smaller than its children and there will be at most log n +1 binomial trees of binomial heap with n nodes.

Screen Shot 2014-06-02 at 2.35.41 PM

Fig 1 : Binomial Heap


Each binomial tree corresponds to one digit in binary representation of a number n.For e.g.the binary representation of 13(Fig 2) is 1101(23+22+20=8+4+1).The binomial heap will have 13 nodes with binomial trees of order 3,2 and 0 respectively.The orders came from the powers of 2. Either there will be no tree or there will one tree of each order i.e we cannot have any two trees of same order in the binomial heap.Similarly for a number like 15,the binary representation is 1111(23+22 +21 +20 =8+4+2+1).The binomial heap will have 15 nodes(Fig 4)with binomial trees of order 3,2,1,0 respectively.

Binomial Heap of 13

Screen Shot 2014-06-02 at 3.11.42 PM

Fig 2 : Binomial Heap of 13


Details of Binomial Heap in Fig 2

Screen Shot 2014-06-02 at 3.14.04 PM

Fig 3 : Details of Binomial Heap in Fig 2


Binomial Heap of 15

Screen Shot 2014-06-04 at 2.42.02 PM

Fig 3 : Binomial Heap of 15


Details of Binomial heap in Fig 3

Screen Shot 2014-06-04 at 2.44.42 PM

Fig 4 : Details of Binomial Heap in Fig 3


Representing Binomial Heaps

The nodes in the binomial heap can be represented by a structure with parent,key,degree,child and sibling attributes ( Fig 5).

Screen Shot 2014-06-05 at 3.41.10 PM

Fig 5 : Structure to represent node of Binomial Heap



Consider the binomial heap as given in Fig 6.Say we want to represent 9(Say) then the structure would be like as given in Fig 7 or if we want represent 31 the structure would be like as given in Fig 8

Screen Shot 2014-06-05 at 3.40.58 PM

Fig 6 : Binomial Heap


Screen Shot 2014-06-05 at 3.44.45 PM

Fig 7 : Structure to represent node 9

Screen Shot 2014-06-05 at 3.46.12 PM

Fig 8 : Structure to represent node 31


Operations on Binomial Heaps

The various operations that can be performed on Binomial heaps are:

  1. Union
  2. Delete Min
  3. Decrease Key
  4. Delete
  5. Insert



Short URL: http://tinyit.cc/de9cf4
By Cusp2207 on June 4, 2014 | Computer Science, Data Structures | A comment?

Binomial Trees

Binomial Trees are one of  the type of trees that are defined  recursively.A Binomial tree of order 0 is a single node and a binomial tree of order n has a root node whose children are roots of binomial trees of order n-1,n-2,n-3,n-4,……3,2,1,0.

Properties of Binomial Tree

  • There are 2n nodes in a binomial tree of order where n is the order and degree of tree(Fig 1).
  • Deleting roots yield binomial trees Bn-1,Bn-2,….0.
  • Bhas \tbinom n d nodes at depth d.

Fig 1 : Binomial Tree

Binomial Tree of height/order(n)=0

When height =0 then single node will be present in Binomial tree(Fig 2).

Screen Shot 2014-05-30 at 3.53.29 PM

Fig 2 : Binomial Tree of Order 0



Binomial Tree at height (n)=1

When n=1 then 2=nodes will be present in the tree(Fig 3).

Screen Shot 2014-05-30 at 4.00.23 PM

Fig 3 : Binomial Tree of order 1



Binomial Tree of order=2

When n=2 then 2= 4 nodes will be present in the tree.The subtree is binomially  attached to the root node(Fig 4).

Screen Shot 2014-05-30 at 4.06.02 PM

Fig 4 : Binomial Tree of order 2



Binomial Tree of order 3

If order of tree is 3,then 23  nodes are present in the Binomial tree.The root is connected to subtrees of order 0(green color),1(red) and 2(black)  (Fig 5).

Screen Shot 2014-05-30 at 4.20.33 PM

Fig 5 : Binomial Tree of order 3



Bn  has  \tbinom n d nodes at depth d.

If we have a binomial tree of order n,then we can trace the number of nodes at any depth by  \tbinom n d.For e.g the no of nodes of binomial tree of order 4 at depth 2 will be 6.(Fig 6).In fig 7,number of nodes at level 2 is 6 and is shown by red highlighted area.

Screen Shot 2014-05-30 at 4.26.02 PM


Screen Shot 2014-05-30 at 4.33.36 PM

Fig 6 : Binomial Tree of order 4

Short URL: http://tinyit.cc/f8eed0
By Cusp2207 on May 30, 2014 | Computer Science, Data Structures | A comment?

Deletion In B-Trees

In order to delete elements from B-Tree we need to ensure that their properties(Refer : http://letslearncs.com/b-trees/ does not get violated.It should remain a binary search tree and number of pointers must be according to the order and keys should be one less than the order in each and every node.


Consider a B-tree of Fig 1.Say we want to delete 2,21,10,3 and 4 step by step from the tree.

Screen Shot 2014-05-29 at 4.58.17 PM

Fig 1 : B-Tree


Delete 2

  • 2 is present in node b.Deletion of 2 do not violate any property of B-tree,so we delete 2 directly from node b.(Fig 2)


Screen Shot 2014-05-29 at 5.02.50 PM

Fig 2 : Delete 2


Delete 21

  • Deletion of 21 cannot be done directly.It causes node e to underflow so elements are redistributed among c,g and e(Fig 3).
    • 10 remains in c.
    • 12 is stored in g and 13 is stored in e.


Screen Shot 2014-05-29 at 5.07.01 PM

Fig 3 : Delete 21


Delete 10

  • Deletion of 10 again cannot be done directly.It causes node c to underflow which further causes parent node g to combine with f and a and tree shrinks by one level.3,7 and 9 are stored in a,1 in b,4 and 5 in d,8 in h ,12 and 13 in e (Fig 4).
Screen Shot 2014-05-29 at 5.15.41 PM

Fig 4 : Delete 10


Delete 3

  • Deletion of 3 causes 4 to move in a (Fig 5).
Screen Shot 2014-05-29 at 5.36.18 PM

Fig 5 : Delete 3


Delete 4

  • Deletion of needs redistribution of the keys in the subtrees of 4; however, nodes b and d do not have enough keys to redistribute without causing an underflow. Thus, nodes b and d are combined together(Fig 6).
Screen Shot 2014-05-29 at 5.47.33 PM

Fig 6 : Delete 4

Short URL: http://tinyit.cc/8bdf8c


The B-tree is a generalization of a binary search tree  in which a node can have more than two children .The B-tree is optimized for systems that read and write large blocks of data.It has following properties

  • The data items are stored at leaves.
  • Every node has between M/2 and M children where M is a positive integer greater than 1.
  • M is the order as well as height of tree.
  • The non leaf nodes store up to M-1 keys.
  • The root is either a leaf or has between two and M children.
  • All leaves are at the same depth and have between [L/2] and L children.

Insertion in B-Tree

The insertion in b-tree is done such that they satisfy all the properties listed above.


Consider a B-Tree of order 4 and we need to insert 5,3,21,9,1,13,2,7,10,12,4,8.Each node can have at most 4 pointers and 3 keys (M-1) or  at least 2 pointers and 1 key.Since it is a binary search tree the keys of left subtree will be less than the root value and keys of right subtree will be greater than root value.

  • Create a node a and insert 5.(Fig 1)
  • Insert 3 to the left of 5 (3<5).
  • Insert 21 to the right of 5(21 >5).
  • In order to insert 9 split node a into b and c as 9 cannot be accommodated in node a(Max keys =3).The left pointer  of 9 points to  3 and 5  ((3 ,5) <9)and the right pointer points to 21(21 >9),
Screen Shot 2014-05-29 at 3.54.56 PM

Fig 1 : Insertion in B-Tree


  • Insert 1 in node b (1<3)(Fig 2).
  • Insert 13 in node c(13>9 and 13 <21).
  • 2 cannot be directly inserted in node b
    • In order to insert 2 split b into b and d.
    • 3 gets stored in  node a.
    • Store 1 and 2 in node b.
    • Store 5 in node d.


Screen Shot 2014-05-29 at 3.55.47 PM

Fig 2 : Insert 1,13,2


  • Insert 7 in node d .(7 >5 and 7<9)(Fig 3)
  • Insert 10 in node c(10 >9 and 10 <13).
  • Now 12 cannot be directly inserted in node c.
    • Split c into c and e.
    • 12 is then inserted in node  c.
    • 21 is stored in e.


Screen Shot 2014-05-29 at 3.56.29 PM

Fig 3 : Insert 7,10,12


  • Insert 4 in node d(4 >3 and 4 <5).(Fig 4)
  • 8 cannot be inserted in d directly.
    • Split d into f and g
    • Split f into f and h.
    • 8 is inserted in h.
Screen Shot 2014-05-29 at 4.26.04 PM

Fig 4 : Insert 4,8


Short URL: http://tinyit.cc/edff9d
By Cusp2207 on May 29, 2014 | Computer Science, Data Structures | 1 comment


The Maxheap sorts the elements in increasing order whereas Minheap sorts the element in decreasing order.To sort the heap three steps have to be followed

  • Heapify -The process picks the largest child key and compare it to the parent key. If parent key is larger than key then heapify quits, otherwise it swaps the parent key with the largest child key. So that the parent  now becomes larger than its children.
  • Build Heap – Use the procedure ‘Heapify’ in a bottom-up fashion to convert an array  into a heap. The process starts from last nodes and not the leaves.
  • Heap Sort – Sorting is done by removing the max element and storing in array .The storage starts from last position and goes till first index of array.

Time Analysis

  • Build Heap Algorithm will run in O(n) time
  • There are n-1 calls to Heapify each call requires O(log n)time
  • Heap sort program combine Build Heap program and Heapify, therefore it has the running time of  O(n log n) time
  • Total time complexity: O(n log n)


Given an array in Fig 1 .We need to convert it to Maxheap and sort it.

Screen Shot 2014-05-21 at 4.44.07 PM

Fig 1 : Array


Array is converted to heap in Fig 2

Screen Shot 2014-05-21 at 4.46.16 PM

Fig 2 : Heap


The further steps are illustrated through following figures

Screen Shot 2014-05-21 at 5.47.08 PM

Step 1

Screen Shot 2014-05-21 at 5.49.53 PM

Step 2

Screen Shot 2014-05-21 at 5.51.09 PM

Step 3

Screen Shot 2014-05-21 at 5.58.18 PM

Step 4

Screen Shot 2014-05-22 at 10.22.04 AM

Step 5

Screen Shot 2014-05-22 at 10.25.05 AM

Step 6


Screen Shot 2014-05-22 at 10.27.29 AM

Step 7


Screen Shot 2014-05-22 at 10.47.37 AM

Step 8

Screen Shot 2014-05-22 at 10.49.30 AM

Step 9

Screen Shot 2014-05-22 at 10.50.36 AM

Step 10

Screen Shot 2014-05-22 at 10.51.45 AM

Step 11

Screen Shot 2014-05-22 at 10.53.55 AM

Step 12

Screen Shot 2014-05-22 at 11.01.39 AM

Step 13

Screen Shot 2014-05-22 at 11.03.13 AM

Step 14

Screen Shot 2014-05-22 at 11.04.04 AM

Step 15

Screen Shot 2014-05-22 at 11.08.46 AM

Step 16

Screen Shot 2014-05-22 at 11.09.40 AM

Step 17

Screen Shot 2014-05-22 at 11.10.35 AM

Step 18

Screen Shot 2014-05-22 at 11.13.24 AM

Step 19

Screen Shot 2014-05-22 at 11.14.41 AM

Step 20


Screen Shot 2014-05-22 at 2.48.53 PM

Step 21

Short URL: http://tinyit.cc/020f01
By Cusp2207 on May 22, 2014 | Computer Science, Data Structures | A comment?

Computer Science
Data Structures