Thursday, July 31, 2008


Definition of a heap

Heap is an almost complete binary tree where the data (key) stored in a node is larger than those of its children nodes. In other words a heap must satisfy following properties :

1. All internal nodes at level 0 to d-2 have degree 2, where d is the depth of the tree.

2. At level d-1, the leaves are all to the right of the internal nodes. The rightmost internal node at level d-1 may have degree 1 which can only be its left child.

3. The key at any node is greater than or equal to the keys of each of its children (if it has any).

Such a heap is called descending heap. In an ascending heap, on the other hand, the key value stored in a node is smaller than the keys of its children nodes. The following figure 19.1 given below depicts a descending heap.

It may be noted, in a descending heap, the root always contains the largest element. The heap is often used for storing priority queues. As we will see later, the complexity of insertion or deletion from a heap is lesser than the corresponding operations with a linear linked list. Moreover, the heap can also be used for sorting an array of elements.

Creation of an initial heap

While creating a heap from a given set of data elements (keys) one has to make sure that the basic properties of a heap must be satisfied. This is illustrated with the help of the following example.

Suppose that the following integer keys are read in a sequence:

5, 25, 2, 70, 49, 29, 129, 30

To begin with when the key 5 is received a single node with this value is created which is by definition is always a heap (shown in the figure 19.2a).

When 25 is now received, it can be attached as a left child of 5 to satisfy that the heap is a complete binary tree. Since the key value of the root is found to be smaller than the key of this newly inserted child, to maintain the descending heap order property the key values are now swapped. This results into a two elements heap as shown in the figure 19.2b.

The next key value received is 2 and the corresponding node is attached as right child of the root node in figure 19.2c. This results in proper heap and no further change is necessary. This process is continued with the subsequent data values and heaps thus created are shown in the following figures (19.2a - 19.2h):

Deletion from a heap

As mentioned before, the root node of a descending heap contains the maximum element. It is this key which is deleted. In order to maintain the heap structure, the key stored in the rightmost leaf node at the bottommost level is selected for insertion into the root node. Since, the key thus entered may not be larger than the data values of its children nodes, to maintain the descending heap property we should exchange it with the larger one of the two children nodes. This process should be continued till the node thus inserted finds its proper place in the heap. This process is called adjust heap. This is illustrated in figure 19.3, where the initial heap is shown figure 19.3a. The key to be deleted is 129 at the root node P. The rightmost leaf node at level 3 (W) has key value 5 and it is to be inserted at node P. Note 5 is smaller than the key values 49 and 70 stored in the children nodes Q and R of P. Hence it is necessary to exchange the key 5 stored in the node P with the key 70 of node R so that the node P has larger key than the keys of its children. At this stage, 5 moves down to node R. Again 5 is smaller than 29 stored in the child node V of R. Therefore, we exchange the keys of the nodes R and V to arrive at the heap shown in the figure 19.3b. The process is now repeated by deleting 70 and inserting the value 5 located in the rightmost child (V) in figure 19.3b. Again it is percolated down the tree so that descending heap property is maintained. This leads to figure 19.3c.

The algorithm for deletion from a heap is described below.

Algorithm : Deletion from a heap.

Input : Heap and a pointer to its root (P).

Output : Heap with one less node containing all the keys from the input heap except the one that was stored in its root.

Method :

Step 1 : Store the key value of the root at a separate place.

Step 2 :Let K be the key stored in the rightmost leaf node at the bottom most level.

Step 3 :Store K into the root (P).

Step 4 : While P is not a leaf do

Let C be the child node of P with the larger key

If K <>

Exchange the key values

Replace P by C



End while

Step 5 :Store K in the node pointed to by P.

The heap adjustment procedure consists of the steps 2 to 5 in the above mentioned algorithm.

Implementation of a heap and heapsort algorithm

Although the binary trees are generally implemented using linked structures as described in section 18.3, an almost complete binary tree can readily be implemented using a simple one dimensional array. This is because the children of a node at a level i of such a tree can be stored at array locations 2i + 1 and 2i + 2 respectively.

Recall that in a heap (an almost complete binary tree) there cannot be any node at level j unless the level j - 1 is completely filled. Therefore according to this mapping scheme the nodes will be stored in the array from left to right and level by level beginning with the root (which is stored at the beginning of the array).

Following this mapping scheme heap in figure 19.1 can be stored in the array shown in figure 19.4

heap[0] heap[4] heap[9]











Fig. 19.4

Based on the mapping scheme mentioned above, an implementation of heapsort algorithm in C is given below. This routine creates an initial heap with the unsorted key values stored in the same array. After that, it successively shifts the maximum element (root) to the bottom of the array and adjust the remaining array so that it returns the heap properly.

EXAMPLE 19.3 :


int x[],n;


int i,data,s,f,ivalue;

/* create initial heap */

for(i=1;i <>



/* insert_heap (x,i,data); */


f=(s - 1) / 2; /* f is the father of s */

while(s > 0 && x[f] <>


x[s]=x[f]; /* move up the tree */


f=(s - 1) / 2; /* f is the father of s */

}/* end while */


}/* end for i.e. a heap has been created */

/* begin repeatedly removing the maximum element i.e. x[0], */

/* place it at the end of the array.*/

/* Convert the remaining part to a heap */

for(i=n - 1; i > 0;i--)


/* delete the root */


x[i]=x[0]; /* the root is placed at the bottom */


/* begin adjusting the heap by pushing the element x[i] i.e. ivalue */

if(i == 1)

s=-1;/* no further processing required */



if(i > 2 && x[2] > x[1])


while(s >=0 && ivalue <>


/* push ivalue down the heap */



/* s=largeson(f, i-1) */

s=2*f +1; /* s is the child of f */

if(s+1 <= i-1 && x[s] <>

s=s+1; /* select the larger of the two children of f i.e. 2j + 1 or 2j + 2 */

if(s > i-1) /* when bounds have been reached */


}/* end while */

/* insert ivalue at fth location */


}/* end for */

}/* end heap sort */

It may be observed, that the entire sorting procedure can be carried out in place, i.e. no separate array is required. It can be shown that the heap adjustment (as well as deletion) procedure has linear complexity i.e. of the order of n (where n is the number of keys). The heapsort algorithm does atmost 2n logn number of comparisons of keys in the worst case.

Sort each of the key sequences given in Quiz #1 using Heapsort. In each case, show the initial heap construction and adjustment of the heap as elements are removed from the heap. Also count the number of comparisons and exchanges made for sorting the key values


The recursive implementation of quicksort algorithm of an array x of n elements involves initial partitioning of the elements into two halves and followed by the recursive invocation of quicksort function once for each half.

The partitioning algorithm works as follows :

Two integer variables l and u are used to locate the leftmost and the rightmost element of the array x under consideration. While the partitioning algorithm will work with any element of the array selected as pivot (element around which partitioning is done) for comparison, in the following example, we have chosen the leftmost element of the array to be the pivot for the sake of simplicity. In the implementation of the quicksort shown in example 19.1, the pivot is stored in the variable k. Initially the variable m is set to the leftmost element of the array. The elements of the array indexed by m i.e. x[m] is successively compared with the pivot element till an element is found which is larger than the pivot (the variable k of the function partition in example 19.1). This is achieved by incrementing m. When such an element is found the comparison is carried out with the bottom half of the array. So, the pivot (k) is now compared with x[n] (n is the variable which is initially set to the bottommost element of the array). The index n is decremented till we find an element which is smaller than the pivot(k). At this stage the elements x[l] and x[n] are exchanged, and the above mentioned procedure is continued till the index m becomes larger than n. At the end the pivot is placed in the location indicated by n. The elements x[l] through x[u] are partitioned so that elements between x[l] and x[j - 1] (where j is the final index of pivot) are less than pivot and all elements between x[j] and x[u] are greater than or equal to pivot.

Example 19.1 :

A recursive implementation of the quicksort algorithm.

void quicksort(int x[], int l, int u)


int * j; int k;

if (l > =u)




partition (x, l,u,&j);

quicksort (x, l, j -1);

quicksort (x, j+1, u);




void partition (int x [], int l, int u,int *j)


int k, m,n, i, temp, int * j;

k = x [l]; /* k is the element whose final */

n = u; /* position is required */

m =l;

while (m <>


while (x[m] <= k && m <>

m++ ; /* move the lower index up */

while (x[n] > k)

n --; /* reduce the upper index */

if (m


/*interchange x[m] & x[n] */




} /* end if */

} * end while */

x[l]= x[n];


* j = n;


} */end partition */.

1. Given the following sequences of integer key values. By selecting appropriate pivot elements, sort each of these sequences in increasing order using quicksort algorithm. In each case, show the intermediate results after partitioning and count the number of comparisons and exchanges made.

a) 2 17 4 19 6 1 75 43 8 21

b) 84 75 68 57 46 34 28 22 14 8

c) 5 7 8 12 43 75 84 88 94 97

d) 5 6 3 18 7 46 28 95 42 98

e) 62 55 44 52 29 36 48 57 68


The recursive invocation of quicksort function involves the creation of a new activation record containing local data, parameters, and various other data items. Further activation of the function quicksort creates a new activation record which would have a different copy of the same data objects, addressed by the Current Environment Pointer (CEP). To avoid the overhead of routine calls in quicksort program in which execution efficiency is a significant consideration, in the following example we illustrate a nonrecursive implementation of the quicksort using a user defined stack. We will be using the stack to push the upper and lower bounds of all sub-arrays those are yet to be sorted. The information pushed in the stack is popped and processing continues until the stack becomes empty.

EXAMPLE 19.2 :

# define STACKSIZE 50

void quicksort(int x[], int n)


int i,j;

struct stack_info{

int l;

int u;


struct stack_tag{

int stacktop;

struct stack_info limits[STACKSIZE];




bounds.u=n - 1;





while(bounds.u > bounds.l)



if((j - bounds.l) > (bounds.u - j))



bounds.u=j - 1;


bounds.l=j + 1;






bounds.l=j + 1;



bounds.u=j - 1;

} /* end if */

} /* end while */

}/* end while */


} /* end quicksort */

int emtpy (struct stack_tag * stackptr)


if( stackptr-> == -1)

return (1);


return (0);

} /* end empty*

void pop (struct stack_tag * stackptr, struct stack_info * data)


if empty (stackptr)


printf (“%s\n”, “stack underflow”);


data=&(stackptr-> limits [stackptr->stacktop]);

-- (stackptr->stacktop);



void push (struct stack_tag * stackptr, struct stack_info *data)


int p;


stackptr->limits[p].l = data->l;

stackptr->limits [p].u = data->u;


} /*end push.; note no checking for stack overflow */

Thursday, July 24, 2008

Data Structures Questions

Data Structures


what is binary search, traversal, hashing etc.

given a scenario what is the suitable data structure.

write a code to count the no. of 1's in a binary rep. of a number.

memory taken for char *, int * etc.

char *cp; int *ip; cp++,ip++ - what is the result.

I was asked about stack,queue,linked list,binary tree,b tree

write code for quick sort. what are the various types of sorting.

( selection sort, merge sort,heap sort,)

Data Structures-Binary,Binary Search Trees

1) What is a data structure?

2) What does abstract data type means?

3) Evaluate the following prefix expression " ++ 26 + - 1324" (Similar types can be asked)

4) Convert the following infix expression to post fix notation ((a+2)*(b+4)) -1 (Similar types can be asked)

5) How is it possible to insert different type of elements in stack?

6) Stack can be described as a pointer. Explain.

7) Write a Binary Search program

8) Write programs for Bubble Sort, Quick sort

9) Explain about the types of linked lists

10) How would you sort a linked list?

11) Write the programs for Linked List (Insertion and Deletion) operations

12) What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?

13) What do you mean by Base case, Recursive case, Binding Time, Run-Time Stack and Tail Recursion?

14) Explain quick sort and merge sort algorithms and derive the time-constraint relation for these.

15) Explain binary searching, Fibinocci search.

16) What is the maximum total number of nodes in a tree that has N levels? Note that the root is level (zero)

17) How many different binary trees and binary search trees can be made from three nodes that contain the key values 1, 2 & 3?

18) A list is ordered from smaller to largest when a sort is called. Which sort would take the longest time to execute?

19) A list is ordered from smaller to largest when a sort is called. Which sort would take the shortest time to execute?

20) When will you sort an array of pointers to list elements, rather than sorting the elements themselves?

21) The element being searched for is not found in an array of 100 elements. What is the average number of comparisons needed in a sequential search to determine that the element is not there, if the elements are completely unordered?

22) What is the average number of comparisons needed in a sequential search to determine the position of an element in an array of 100 elements, if the elements are ordered from largest to smallest?

23) Which sort show the best average behavior?

24) What is the average number of comparisons in a sequential search?

25) Which data structure is needed to convert infix notations to post fix notations?

26) What do you mean by:

27) Syntax Error

28) Logical Error

29) Runtime Error

30) How can you correct these errors?

31) In which data structure, elements can be added or removed at either end, but not in the middle?

32) How will inorder, preorder and postorder traversals print the elements of a tree?

33) Parenthesis are never needed in prefix or postfix expressions. Why?

34) Which one is faster? A binary search of an orderd set of elements in an array or a sequential search of the elements.

where do you use double linked list. (queing the prosess in cpu).

write a program to accept name & sort them.

Datastructures esp :Linked list and trees

Construct a doubly linked list using a single pointer in each node

Wednesday, July 16, 2008

Data Structures FAQ's

1. Simple Questions.
1) When we talk about linked lists, does it have to do with (choose the most
closely related item):
i. data types (such as priority queues)
ii. goals (such as adaptability)
iii. implementation (of, say, a sequence)
2) Underscore the line(s) (if any) in the following code which potentially break
the principle of encapsulation:
class Node {
public Object element;
public Node next;
Node() { this(null, null); }
void setNext(Node newText) { next = newText; }
Node getNext() { return next; }
3) What is the primary reason to use quadratic probing instead of linear probing?
(choose the most closely related item):
i. Easier to expand the hash table when it gets full
ii. To avoid the primary cluster which may cause excessive data collision
iii. Achieve the same search time with less memory
iv. Easier to support delete
4) Suppose that there are N distinct elements in a binary heap (with the maximum
at the root). Which positions could possibly be occupied by the fourth largest
i. 1
ii. 2 or 3
iii. 4 through 7
iv. 2 through 15
v. 16 and higher
5) Characterize, using the big-Oh notation, the worst-case running time of the
following algorithm:
Let A be a given array of n integers.
for i <- 0 to n-1 do
for j <- 0 to (i*i)-1 do
Let A[j mod n] <- j.
end for
end for
Best characterization: O(_______).
2. (Linked list) Recall we did singly linked list in PA #4. To refresh your memory,
· Consider a list with elements (1,2,3,4,5)
· The list will be like 1 2345
Singly linked list doesn’t have loops. Suppose your friend (call him Bob)
has inadvertently introduced a loop into his implementation on PA #4
· Consider a list with elements (1,2,3,4,5)
· Let 3 point to 1 instead of pointing to 4
· The list will be like 1 23 45
Since most of your friends suffer from the same bug while implementing PA#4
you decide to help them by writing a function which detects loops in a singly
linked list.
· Write program that outputs ‘false’ if there is no loop in the list input and
‘true’ if there is a loop in a list output
· Fill in the following code
o class list_sorted {
// You need to implement this
bool FindLoop() {
node* pHead;
o struct node{
int x;
node* next;
· Hint:
o Change the node data structure. Have some sort of counter which
indicates how many times a node is visited when you traverse through
the link list.
o There might be better ideas than this!
3. (Hash table) You have a hash table of size m = 11 and two has functions h1 and h2:
h1(x) = (sum of the values of the first and last letters of x) mod m
h2(x) = ((value of the last letter) mod (m – 1)) + 1
Where the value of a letter is its position in the alphabet, as in the following table:
a b c d e f g h i g k l m
1 2 3 4 5 6 7 8 9 10 11 12 13
n o p q r s t u v w x y z
14 15 16 17 18 19 20 21 22 23 24 25 26
1) Draw a picture of the resulting hash table after inserting the following words (by
the order):
ibex, hare, ape, bat, koala, mud, dog, carp, stork
2) Highlight cells that are looked at when trying to find bird. Do this for each of the
following techniques.
Chaining with h1 as your hash function.
Linear probing with h1 as your hash function.
4. (Heap) Give an algorithm for changing the value of an arbitrary element from a heap
of size N. Also, determine the worst case time complexity of your algorithm.
Describe your algorithm in pseudo-code. You may assume that the position of the
element whose value to be changed is given.
5. (Binary tree) Let T be a binary tree.
1) If T has seven nodes, what is its minimum height?
What is its maximum height?
Draw two trees with seven nodes that achieve the minimum and maximum height,
2) When deleting a node of a binary search tree, if we decide to replace it with a
node in its left subtree (of course, if it has one), which node should we choose?
3) A particular binary search tree has the following known about it:
A pre-order traversal yields 88, 6, 1, 3, 2, 5, 4, 30, 10, 20.
A post-order traversal yields 2, 4, 5, 3, 1, 20, 10, 30, 6, 88.
Draw this tree.
4) What is the in-order traversal of the tree from 3)?
5) Using the node values from 3), draw a minimal-height BST. Make it a complete
6. (Inheritance) Consider at the following code [each class is in the appropriately
named file]:
class Animal {
virtual void describe() {
class Rabbit: public Animal {
Rabbit() { Animal(); }
void describe() {
void hop () {
System.out.println ("Hop");
class Dog: public Animal {
Dog() {}
void describe() {
class Poodle: public Dog {}
1) List all constructors called for each line.
Code Constructor Calls
Animal a = new Dog();
Rabbit r = new Rabbit();
Poodle p = new Poodle();
Animal a2 = a;
2) What is output of the following lines? If it is a CT / RT exception, say
so. Assume each line is executed independently (no cascading errors).
Code Output
(new Animal()).describe();
(new Rabbit()).describe();
(new Dog()).describe();
(new Poodle()).describe();
Animal a = new Rabbit();
Animal b = new Rabbit();
7. (String searching) This question is about the problem of searching for any
occurrence of an M-character pattern in an N-character text string. Suppose that
student X uses the brute-force method and student Y uses the right-left scan. The
students are each given the option of picking from among one of the three string
generators listed below for both programs to be tested on (both pattern and text to be
generated from the same generator, then both programs invoked on the same input).
A. random string of As and Bs
B. random ASCII characters
C. all As except last character is B
Fill in the blanks to give the best choice and expected results from each students' point of
view. (If the asymptotic number of character compares is the same, answer "1".)
(a) For X's choice _______, brute-force is a factor of _______ faster than right-left.
(b) For Y's choice _______, right-left is a factor of _______ faster than brute-force.
8. (Operator overloading) Provide the declarations of the overloaded operator+ for F1
that will permit the two add operations shown in main().
class F1 {
int data;
F1 a;
9. Indicate true or false.
class A1 {
int a;
char* name;
A1(char* n){name=new char[strlen(n)+1];
memcpy(name, n, strlen(n)+1);}
int b;};
class D1 : public A1{
int data;
class D2 : private A1{};
a. The “public” constructor for A1 allocates memory from global heap for the
private member “name” therefore “name” can be direcly accessed by class D2,
which is derived from A1.
b. Since D2 inherits A1 as a public class, both the private members of A1 are
directly accessible within D2.
10. (set) Suppose the set s is declared with
set s;
Write the definition of the function removeOdd() that will remove all odd integers
belonging to s with the call
11. (doubly linked list) (a) Why do some programmers like to have dummy nodes at
each end of a doubly linked list? (b) What are the disadvantages of having dummy nodes
at the beginning of the list?
12 (map) Suppose we want a data structure that allows us to look up a person's name and
address from his or her social security number. (a) How would you use an STL map for
this? (b) How long does it take to access the name and/or address from a social security
number in this data structure?