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 .

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)

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"

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)