heap Implementation in c++

hey, I am trying to implement a minHeap data structure in c++. I have made a heap class.But I am a bit confused in completing a function named decreaseKey(int v, float k) − This operation decrease the key value of the vertex v to k. How can I do this? My code is given below. Please help



class HeapItem
{
public:
int vertex;
float key;
};

class MinHeap
{
public:
HeapItem * A; //stores heap items, e.g., nodes
int heapLength;
int * map;

MinHeap()
{
A = new HeapItem[MAX_HEAP_SIZE];
map = new int[MAX_HEAP_SIZE];
heapLength=0;
}

~MinHeap()
{
if (map) delete [] map;
if (A) delete [] A;
}

void initialize(int v[], int n)
{
heapLength = n;
for(int i=0;i<n;i++) //nodes are stored from index 1
{ //in the heap
A[i+1].vertex = v[i];
A[i+1].key = MAXREAL;
map[v[i]] = i+1;
}
}


void decreaseKey(int v, float key) //I have to implement this
{

}

void heapify(int i)
{
int l,r,smallest;
while(1)
{
l=2*i; //left child index
r=2*i+1; //right child index
smallest=i;
if (l>heapLength && r>heapLength)
break; //nothing to do, we are at bottom
else if(r>heapLength)
smallest = l;
else if(l>heapLength)
smallest = r;
else if( A[l].key < A[r].key )
smallest = l;
else
smallest = r;

if(A[i].key <= A[smallest].key)
break; //we are done heapifying
else
{
//swap nodes with smallest child
HeapItem t;
t=A[i];
A[i]=A[smallest];
map[A[i].vertex]=i;
A[smallest]=t;
map[A[smallest].vertex]=smallest;
i=smallest;
}

} //End while
}
// End Heapify

};
Why multiple arrays are required in your code?
If you want an indexed container having key and value use a STL provided map which keeps key and value pair together.
There are well implemented methods in the map class for comparison , swap and other required function which you are doing it manually here.
Read below about map .
http://www.cplusplus.com/reference/map/map/
@Rabindra Hota
He is trying to implement a heap data structure, not a balanced search tree...
Topic archived. No new replies allowed.