Friday, January 11, 2008

Floating in a Tree

If you have a priority queue setup of many nodes. Lets say we want to bring the node with the highest value to the top . IN orther words if i have given a heap than how do i modify the heap so that the biggest element is always present at the root.

One simple logic can be . Given a root node of a subtree .

  • Assume the root node is the largest node .
  • Now compare the value of root node with left child and mark the one with the bigger value as biggest
  • Then compare biggest with the right child now and make the bigger of the two as the new biggest.
  • now repeat the above mentioned steps with the new largest node
In terms of code this looks like :

void maxHeapify(int * a,int rootIndex, int heapLength){
int largest = rootIndex;
int leftIndex = left(rootIndex);
int rightIndex = right(rootIndex);

if(leftIndex < heapLength && a[rootIndex] < a[leftIndex]){
largest = leftIndex;
}
if(rightIndex < heapLength && a[largest] < a[rightIndex]){
largest = rightIndex;
}
if(largest != rootIndex){
swap(a[largest],a[rootIndex]);
maxHeapify(a,largest,heapLength);
}
}

The worst case time for floating a node to any another node depending on your optimization would be approximately equal to the height of the tree , which would generally result in something like ~ lg(N) . To give a counter example for a max Heap operating in a heap . lets give a value of 0 to the root , and let all the other nodes be 1 . In that case the program would go all the way down the heap till the last leaf .

Thursday, January 10, 2008

casts in C++

C++ provides us with 4 types of casting mechanisms . Namely:
  1. static_cast
  2. const_cast
  3. dynamic_cast
  4. reinterpret_cast
static_cast

In C casting is done via () operator

int i = 7;
e.g double d = (double) i;

in c++ to do something like this one should use static_cast .
e.g double d = static_cast<double>(i);

const_cast

const_cast is used to remove constness of an object .

jump(Person * person);

Person p;
const Person& constPerson = p;

then some thing like this wont work.
jump(&constPerson) , cause jump expects a non const object . To fix this you would have to use something like this.

jump(const_cast<person*>(&constPerson));

dynamic_cast

This cast is used with inheritance hierarchies . Say to cast a between pointers or references of base classes to references or pointers of derived classes.

e.g

Mammal * mammal;

jump(dynamic_cast<person*>(mammal));

if there was a function like

jump(Person& person); then

we would have something like

jump(dynamic_cast<person&>(*mammal));

if the casting is not possible , the dynamic_cast mechaism throws an excetion or the result is null (This is implementation specific)

Wednesday, January 09, 2008

Little Sugar: C++ references

C++ references are a variant of const pointers that always point to something .

Now consider

string s1("abc");

string s2("def");

string & refTos1 = s1;

Now refTosi points to s1.

Even after refTos1 = s2. Its still points to s1 . But the value of s1 is now changed from "abc" to "def"

Tuesday, January 08, 2008

Little Sugar : Big Oh

Consider a scenario where you had a list of N numbers . Now say you have an algorithm that finds the does some sort of comparison . If comparison strategy used compares every element with all the succeeding elements . Then on an average the number of comparisons possible in different cases would be something like this :

(n) + (n-1) + (n-2) .... 1

for the 1 st case we have n comparisons
for the 1 st element we have n-1 comparisons
for the 2 nd element we have n-2 comparison .. and so on.

the sum is = ((n)*(n+1))/2 = O(n^2)