c++ - Minimum heap via array representation of a binary tree; MoveDown function loops infinitely -
i working on implementing minimum heap using array datastructure, having issue movedown method (used @ root node return collection heap if root's children every smaller it). assume reader know min heap is, i'll describe in case not or understanding incorrect.
a minimum heap (in case) binary tree represented array such that:
- the root node smallest value in datastructure
- a node must smaller it's children
- given node of array index i, it's left child @ index i*2 + 1 , right child @ i*2 + 2
the current issue having movedown function runs infinite loop when swapping. having difficult time finding logic error, fear might closer root (pun intended, couldn't myself).
notable data members of heap.cpp file:
int size; minivector array;// implementing custom array void movedown(int root);
movedown function in heap.cpp file:
void binaryheap::movedown( int root ){ int temp = root; int templc = temp*2 + 1;//leftchild int temprc = temp*2 + 2;//rightchild //not leaf while( ( templc < array.size() && temprc < array.size() ) && ( (array[temp] > array[templc]) || (array[temp] > array[temprc]) ) ){ int hold = array[temp]; if( array[temp] > array[temprc] ){ array[temp] = array[temprc]; array[temprc] = hold; temp = temprc; } else{ array[temp] = array[templc]; array[templc] = hold; temp = templc; } int templc = temp*2 + 1;//leftchild int temprc = temp*2 + 2;//rightchild } }
you redeclare variables. @ bottom of while loop
int templc = temp*2 + 1;//leftchild int temprc = temp*2 + 2;//rightchild
should be
templc = temp*2 + 1;//leftchild temprc = temp*2 + 2;//rightchild
wouldn't happen in java.
also wouldn't happen if rewrote loop infinite loop break in middle
for (;;) { int templc = temp*2 + 1;//leftchild int temprc = temp*2 + 2;//rightchild if (...) break; ... }
but flamed whenever suggest kind of loop idea. last time suggested 'almost anti-pattern' , 1 of more polite responses.
Comments
Post a Comment