Programming Forums > Application Development > C++

cwl157 · Apr 1st, 2006, 5:00 PM

i don't know. A min heap just fills them up left to right. I was told if you take the number of times something has been entered like keep a counter. Like if you enter the numbers 12, 14, 19 the counter would be 3 because 3 numbers have been entered. Then if you take the binary representation of that counter number it tells you where the next one should go. You put the binary numbers into an array and then look at each 1 or 0 ignoring the most significant 1. And then if the next number in the array is 1 move right if its 0 move left. Then when the numbers done wherever it is thats where the new value goes. Then you compare that value to the parents and swap accordingly. Is there a different easier way to keep track of the insert spot? I really need help because this has to be done by tuesday and i do not even have the insert done.

The Dark · Apr 1st, 2006, 5:07 PM

Ah, I see. Where you are going wrong is the difference between this part of the expanation

Quote:

Then if you take the binary representation of that counter number it tells you where the next one should go.

And your code, which is getting the binary representation of the value that you are entering.

You need to use the binary representation of counter, not option

I'll post some code changes in a bit.

nnxion · Apr 1st, 2006, 5:42 PM

Quote:

Originally Posted by The Dark

Ah, I see. Where you are going wrong is the difference between this part of the expanation

And your code, which is getting the binary representation of the value that you are entering.

You need to use the binary representation of counter, not option

I'll post some code changes in a bit.

What binary representation? You mean keeping a list of the whole heap?

DaWei, grumpy, jim mcnamara, and you The Dark are my programming examples (way more experienced and advanced than me). And so am interested in how you would handle such a thing.

Quote:

"To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master."

In my case, I just have 4 "programming masters".

cwl157 · Apr 1st, 2006, 6:16 PM

like you take the counter and mod it by 2 and then devide the counter by 2 and mod the new counter and then keep going until the counter is 0 and then you take each of those mod 2 numbers which each will be a 0 or 1 and put them into an array. Then you ignore the most significant 1 and all 0 before it and take the rest of the 1 and 0 s and they tell you which way to go to insert the next value

The Dark · Apr 1st, 2006, 6:42 PM

@nnxion: I am not ignoring your examples, yours is the way I would do it (actually I would probably use arrays), but the OP seems to have to do it this way. I did a bit of googling to try to understand what he was getting at.
Basically for this type of min-heap, you always insert at the bottom in the next available spot and then percolate back up, that way the heap is always balanced. For an array implementation, the next available spot is just the entry just after the end of the current array. For this implementation, looking at the number of items counter as binary left/right indicators is a "quick" way of traversing down the tree to get to the next available location.

@cwl157: here are some changes to get you going.
1. In setLeft

(Toggle Plain Text)

  void setLeft(heapNode *newLeft)
  {
    right = newLeft;
  }

You really need to put left here. Otherwise nothing will work.

2. In print()

(Toggle Plain Text)

  void print()
  {
    cout << root->left
         << root->right;
    if(root->left != NULL && root->right != NULL)
    {
      print();
    }
  }

This will always recurse infinitely for any heap with more than one entry.
My code loos like:

(Toggle Plain Text)

  void print()
  {
    printNode(root, 0);
  }

  void printNode(heapNode *node, int level)
  {
    if (node != NULL)
    {
      cout << "Level: " << level << " Val: " << node->getValue() << "\n";
      printNode(node->getLeft(), level + 1);
      printNode(node->getRight(), level + 1);
    }
  }

3. In main

(Toggle Plain Text)

  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    }

This code always inserts the 0 value before exitting the loop, you should test for 0 before inserting into the heap.

4. At the moment you are creating a new node in each level of your recursion, this is bad (and is one of the things that confused me in the first place). Create the node in "insertSpot" and pass it in to your function

(Toggle Plain Text)

  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);

5. Change your binary left/right array calculation to use the counter rather than "option" (option is a funny name for that parameter btw).

(Toggle Plain Text)

      int temp = counter;
      for(i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          temp = temp / 2;
          ar[i] = arrayValue;
      }

6. You don't increment the counter variable anywhere, but you need to now that you are using it. It looks to me as if you need to add it before you start looking at the left/right binary, so that the second item added goes to the left of the root (2 = 0010 in binary).

(Toggle Plain Text)

  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    // Increment counter first as the algorithm needs it
    counter++;

7. I wasn't sure how the whole left/right binary thing would work when there was no entries in the heap, so I made a special case for that

(Toggle Plain Text)

  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    // Increment counter first as the algorithm needs it
    counter++;

    if (root == NULL)
    {
      root = newNode;
    }
    else
    {

8. The realInsert function needs to have access to all of the array, not just the first entry (as I said before).
It also needs to know which parent node in the heap it is working on (currently yours works on a newly created node, which has nothing to do with the heap).
It also needs the new node created in insertSpot (from #4).

(Toggle Plain Text)

  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)

Give it a go and see how you progress.

What environment are you working in? If you have a debugger, you should single step through the program to see what it does. If you don't have a debugger, you should put trace writes through your code. For example, call the heap print function at various stages to see how it goes.

cwl157 · Apr 1st, 2006, 7:26 PM

im using emacs editor on a unix server. I do not really know completely how to use it. Thanks for all the suggestions ill make the changes and see what happens

cwl157 · Apr 1st, 2006, 7:44 PM

alright these are the errors i got after entering the new stuff i will try and work them out but i thought i would post them anyway:

Quote:

program5.cpp:221: error: expected `}' at end of input
program5.cpp: In member function ?void heap::realInsert(int*, int, heapNode*, heapNode*)?:
program5.cpp:79: error: declaration of ?heapNode* newNode? shadows a parameter
program5.cpp:80: error: ?newValue? was not declared in this scope
program5.cpp: In member function ?void heap::insertSpot(int)?:
program5.cpp:128: warning: name lookup of ?i? changed
program5.cpp:108: warning: matches this ?i? under ISO standard rules
program5.cpp:117: warning: matches this ?i? under old rules
program5.cpp:136: error: no matching function for call to ?heap::realInsert(int&, int&, int&)?
program5.cpp:77: note: candidates are: void heap::realInsert(int*, int, heapNode*, heapNode*)
program5.cpp:141: error: a function-definition is not allowed here before ?{? token
program5.cpp:146: error: a function-definition is not allowed here before ?{? token
program5.cpp:157: error: a function-definition is not allowed here before ?{? token
program5.cpp: In member function ?int heap::main()?:
program5.cpp:219: error: ?class heap? has no member named ?print?
program5.cpp: At global scope:
program5.cpp:221: error: expected unqualified-id at end of input

My biggest qestion is when calling realInsert what do i pass for the parent and newNode because i only declare one node?

cwl157 · Apr 1st, 2006, 8:03 PM

alright now i got it down to this and im stuck

Quote:

program5.cpp: In member function ?void heap::realInsert(int*, int, heapNode*, heapNode*)?:
program5.cpp:79: error: ?newValue? was not declared in this scope
program5.cpp: In member function ?void heap::insertSpot(int)?:
program5.cpp:127: warning: name lookup of ?i? changed
program5.cpp:107: warning: matches this ?i? under ISO standard rules
program5.cpp:116: warning: matches this ?i? under old rules
program5.cpp:135: error: ?parent? was not declared in this scope

The Dark · Apr 2nd, 2006, 4:38 AM

It is pretty hard to suggest how to fix errors when I can't see your code, but here goes:

Quote:

program5.cpp: In member function ?void heap::realInsert(int*, int, heapNode*, heapNode*)?:
program5.cpp:79: error: ?newValue? was not declared in this scope

This would be because there is no longer a newValue parameter to realInsert. You don't need the value, because we have already created the node (at the top of insertSpot). You don't have to do it this way of you don't want to, you could leave the creation of the new node to realInsert, but you would need to make sure that you only create the node at the lowest level (i.e. when pos is 0), if you want to do it that way, then just pass the value in rather than the new node.

Quote:

program5.cpp: In member function ?void heap::insertSpot(int)?:
program5.cpp:127: warning: name lookup of ?i? changed
program5.cpp:107: warning: matches this ?i? under ISO standard rules
program5.cpp:116: warning: matches this ?i? under old rules

This is due to your having a variable called i declared at the top of your function and also declaring it again inside your for loops. Either use a different variable name, or move the declaration of the variable to below the for loop.

Quote:

program5.cpp:135: error: ?parent? was not declared in this scope

parent is the name of the parameter, you should pass in root in the first call to realInsert, as root is the top level parent of the heap.

As to what to pass as parent and newNode. When you first call the realInsert function the parent would be root, from then on when you recurse down, you would use parent->getLeft() or parent->getRight().
Pass in the newNode that was created at the top of insertSpot as the newNode parameter.

cwl157 · Apr 2nd, 2006, 6:46 AM

sorry i will post the whole code with the changes i made:

(Toggle Plain Text)

#include <iostream>
using namespace std;

class heapNode
{
  private:
  int value;
  //heapNode *left;
  //heapNode *right;

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

  //set value
  void setValue(int newValue)
  {
    value = newValue;
  }

  // set right
  void setRight(heapNode *newRight)
  {
    right = newRight;
  }

  // set left
  void setLeft(heapNode *newLeft)
  {
    left = newLeft;
  }
  
}; // end of heapNode class

class heap
{
  private:
  heapNode *root;
  int counter;

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    newNode = new heapNode(newValue);
    if(newNode->left == NULL)
    {
      realInsert(ar, pos-1, parent, newNode);
      if(newNode->left->getValue() < newNode->getValue())
      {
        newNode->setValue(newNode->left->getValue());
        counter++;
      }  
    }
    else if(newNode->right == NULL)
    {
      realInsert(ar, pos-1, parent, newNode);
      if(newNode->right->getValue() < newNode->getValue())
      {
        newNode->setValue(newNode->right->getValue());
        counter++;
      }
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    int arrayValue;
    bool isOne = false;
    int ar[32];
    int i = 31;
    int temp = counter;
    counter++;
    if(root == NULL)
    {
      root = newNode;
    }
    else
    {
      for(int i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          option = temp / 2;
          ar[i] = arrayValue;
      }
 
      for(int i = 0; i < 32; i++)
        cout << ar[i] << " ";
      cout << endl;

      while(i >= 0)
      {
        if(ar[i] == 1)
          isOne = true;
        if(isOne = true)
          break;
        i--;
      }
      realInsert(*ar, i, parent, newNode);
    }
  }
   
  //print
  void print()
  {
    printNode(root, 0);
  }

  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
      cout << "Level: " << " Val: " << node->getValue() << "\n";
      printNode(node->getLeft(), level + 1);
      printNode(node->getRight(), level + 1);
    }
  }

  // get root
  heapNode* getRoot()
  {
    return root;
  }

  //insert a new value into the heap
  // void insert(int value, heapNode *newNode)
  //{
  //  if(counter == 0)
  //  {
  //    newNode = new heapNode(value);
  //    root = newNode;
  //  }
  //  else
  //  {
  //    insertSpot(counter);
  //    newNode = new heapNode(value);
  //  }
    //while(newNode.getValue() != root.getValue())
    //{
      //if(newNode > parent)
        //break;
      //elseif(newNode < parent)
        //counter-1 node.setValue(newNode.getValue());
    // }
  //   counter++;
  // }

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    }

  myHeap->print();
  return 0;
}

#include <iostream>
using namespace std;

class heapNode
{
  private:
  int value;
  //heapNode *left;
  //heapNode *right;

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

  //set value
  void setValue(int newValue)
  {
    value = newValue;
  }

  // set right
  void setRight(heapNode *newRight)
  {
    right = newRight;
  }

  // set left
  void setLeft(heapNode *newLeft)
  {
    left = newLeft;
  }
  
}; // end of heapNode class

class heap
{
  private:
  heapNode *root;
  int counter;

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    newNode = new heapNode(newValue);
    if(newNode->left == NULL)
    {
      realInsert(ar, pos-1, parent, newNode);
      if(newNode->left->getValue() < newNode->getValue())
      {
        newNode->setValue(newNode->left->getValue());
        counter++;
      }  
    }
    else if(newNode->right == NULL)
    {
      realInsert(ar, pos-1, parent, newNode);
      if(newNode->right->getValue() < newNode->getValue())
      {
        newNode->setValue(newNode->right->getValue());
        counter++;
      }
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    int arrayValue;
    bool isOne = false;
    int ar[32];
    int i = 31;
    int temp = counter;
    counter++;
    if(root == NULL)
    {
      root = newNode;
    }
    else
    {
      for(int i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          option = temp / 2;
          ar[i] = arrayValue;
      }
 
      for(int i = 0; i < 32; i++)
        cout << ar[i] << " ";
      cout << endl;

      while(i >= 0)
      {
        if(ar[i] == 1)
          isOne = true;
        if(isOne = true)
          break;
        i--;
      }
      realInsert(*ar, i, parent, newNode);
    }
  }
   
  //print
  void print()
  {
    printNode(root, 0);
  }

  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
      cout << "Level: " << " Val: " << node->getValue() << "\n";
      printNode(node->getLeft(), level + 1);
      printNode(node->getRight(), level + 1);
    }
  }

  // get root
  heapNode* getRoot()
  {
    return root;
  }

  //insert a new value into the heap
  // void insert(int value, heapNode *newNode)
  //{
  //  if(counter == 0)
  //  {
  //    newNode = new heapNode(value);
  //    root = newNode;
  //  }
  //  else
  //  {
  //    insertSpot(counter);
  //    newNode = new heapNode(value);
  //  }
    //while(newNode.getValue() != root.getValue())
    //{
      //if(newNode > parent)
        //break;
      //elseif(newNode < parent)
        //counter-1 node.setValue(newNode.getValue());
    // }
  //   counter++;
  // }

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    }

  myHeap->print();
  return 0;
}

Apr 1st, 2006, 6:42 PM	#45
The Dark Expert Programmer Join Date: Jun 2005 Posts: 824 Rep Power: 4	@nnxion: I am not ignoring your examples, yours is the way I would do it (actually I would probably use arrays), but the OP seems to have to do it this way. I did a bit of googling to try to understand what he was getting at. Basically for this type of min-heap, you always insert at the bottom in the next available spot and then percolate back up, that way the heap is always balanced. For an array implementation, the next available spot is just the entry just after the end of the current array. For this implementation, looking at the number of items counter as binary left/right indicators is a "quick" way of traversing down the tree to get to the next available location. @cwl157: here are some changes to get you going. 1. In setLeft (Toggle Plain Text) void setLeft(heapNode newLeft) { right = newLeft; } void setLeft(heapNode newLeft) { right = newLeft; } You really need to put left here. Otherwise nothing will work. 2. In print() (Toggle Plain Text) void print() { cout << root->left << root->right; if(root->left != NULL && root->right != NULL) { print(); } } void print() { cout << root->left << root->right; if(root->left != NULL && root->right != NULL) { print(); } } This will always recurse infinitely for any heap with more than one entry. My code loos like: (Toggle Plain Text) void print() { printNode(root, 0); } void printNode(heapNode node, int level) { if (node != NULL) { cout << "Level: " << level << " Val: " << node->getValue() << "\n"; printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); } } void print() { printNode(root, 0); } void printNode(heapNode node, int level) { if (node != NULL) { cout << "Level: " << level << " Val: " << node->getValue() << "\n"; printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); } } 3. In main (Toggle Plain Text) while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); } while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); } This code always inserts the 0 value before exitting the loop, you should test for 0 before inserting into the heap. 4. At the moment you are creating a new node in each level of your recursion, this is bad (and is one of the things that confused me in the first place). Create the node in "insertSpot" and pass it in to your function (Toggle Plain Text) void insertSpot(int option) { heapNode newNode = new heapNode(option); void insertSpot(int option) { heapNode newNode = new heapNode(option); 5. Change your binary left/right array calculation to use the counter rather than "option" (option is a funny name for that parameter btw). (Toggle Plain Text) int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar[i] = arrayValue; } int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar[i] = arrayValue; } 6. You don't increment the counter variable anywhere, but you need to now that you are using it. It looks to me as if you need to add it before you start looking at the left/right binary, so that the second item added goes to the left of the root (2 = 0010 in binary). (Toggle Plain Text) void insertSpot(int option) { heapNode newNode = new heapNode(option); // Increment counter first as the algorithm needs it counter++; void insertSpot(int option) { heapNode newNode = new heapNode(option); // Increment counter first as the algorithm needs it counter++; 7. I wasn't sure how the whole left/right binary thing would work when there was no entries in the heap, so I made a special case for that (Toggle Plain Text) void insertSpot(int option) { heapNode newNode = new heapNode(option); // Increment counter first as the algorithm needs it counter++; if (root == NULL) { root = newNode; } else { void insertSpot(int option) { heapNode newNode = new heapNode(option); // Increment counter first as the algorithm needs it counter++; if (root == NULL) { root = newNode; } else { 8. The realInsert function needs to have access to all of the array, not just the first entry (as I said before). It also needs to know which parent node in the heap it is working on (currently yours works on a newly created node, which has nothing to do with the heap). It also needs the new node created in insertSpot (from #4). (Toggle Plain Text) void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) Give it a go and see how you progress. What environment are you working in? If you have a debugger, you should single step through the program to see what it does. If you don't have a debugger, you should put trace writes through your code. For example, call the heap print function at various stages to see how it goes.

Apr 2nd, 2006, 6:46 AM	#50
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 333 Rep Power: 4	sorry i will post the whole code with the changes i made: (Toggle Plain Text) #include <iostream> using namespace std; class heapNode { private: int value; //heapNode left; //heapNode right; public: heapNode left; heapNode right; //constructor heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } //get value int getValue() { return value; } //get right heapNode* getRight() { return right; } //get left heapNode* getLeft() { return left; } //set value void setValue(int newValue) { value = newValue; } // set right void setRight(heapNode newRight) { right = newRight; } // set left void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: //constructor heap() { counter = 0; root = NULL; } void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) { newNode = new heapNode(newValue); if(newNode->left == NULL) { realInsert(ar, pos-1, parent, newNode); if(newNode->left->getValue() < newNode->getValue()) { newNode->setValue(newNode->left->getValue()); counter++; } } else if(newNode->right == NULL) { realInsert(ar, pos-1, parent, newNode); if(newNode->right->getValue() < newNode->getValue()) { newNode->setValue(newNode->right->getValue()); counter++; } } } // find the spot to put new value void insertSpot(int option) { heapNode newNode = new heapNode(option); int arrayValue; bool isOne = false; int ar[32]; int i = 31; int temp = counter; counter++; if(root == NULL) { root = newNode; } else { for(int i = 0; i < 32; i++) { arrayValue = temp % 2; option = temp / 2; ar[i] = arrayValue; } for(int i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; while(i >= 0) { if(ar[i] == 1) isOne = true; if(isOne = true) break; i--; } realInsert(ar, i, parent, newNode); } } //print void print() { printNode(root, 0); } void printNode(heapNode node, int level) { if(node != NULL) { cout << "Level: " << " Val: " << node->getValue() << "\n"; printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); } } // get root heapNode* getRoot() { return root; } //insert a new value into the heap // void insert(int value, heapNode newNode) //{ // if(counter == 0) // { // newNode = new heapNode(value); // root = newNode; // } // else // { // insertSpot(counter); // newNode = new heapNode(value); // } //while(newNode.getValue() != root.getValue()) //{ //if(newNode > parent) //break; //elseif(newNode < parent) //counter-1 node.setValue(newNode.getValue()); // } // counter++; // } / int delete(rootValue) { heapNode tempNode = new heapNode(value, left, right) go down the heap to the last one make it root last nodeValue = null while(not at the bottom level of tree) { if(newRoot < left) break; elseif(newRoot > left) swap with left; } return tempNode; } / }; // end of heap class int main() { heap myHeap; myHeap = new heap(); int option=9; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); } myHeap->print(); return 0; } #include <iostream> using namespace std; class heapNode { private: int value; //heapNode left; //heapNode right; public: heapNode left; heapNode right; //constructor heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } //get value int getValue() { return value; } //get right heapNode getRight() { return right; } //get left heapNode* getLeft() { return left; } //set value void setValue(int newValue) { value = newValue; } // set right void setRight(heapNode newRight) { right = newRight; } // set left void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: //constructor heap() { counter = 0; root = NULL; } void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) { newNode = new heapNode(newValue); if(newNode->left == NULL) { realInsert(ar, pos-1, parent, newNode); if(newNode->left->getValue() < newNode->getValue()) { newNode->setValue(newNode->left->getValue()); counter++; } } else if(newNode->right == NULL) { realInsert(ar, pos-1, parent, newNode); if(newNode->right->getValue() < newNode->getValue()) { newNode->setValue(newNode->right->getValue()); counter++; } } } // find the spot to put new value void insertSpot(int option) { heapNode newNode = new heapNode(option); int arrayValue; bool isOne = false; int ar[32]; int i = 31; int temp = counter; counter++; if(root == NULL) { root = newNode; } else { for(int i = 0; i < 32; i++) { arrayValue = temp % 2; option = temp / 2; ar[i] = arrayValue; } for(int i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; while(i >= 0) { if(ar[i] == 1) isOne = true; if(isOne = true) break; i--; } realInsert(ar, i, parent, newNode); } } //print void print() { printNode(root, 0); } void printNode(heapNode node, int level) { if(node != NULL) { cout << "Level: " << " Val: " << node->getValue() << "\n"; printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); } } // get root heapNode* getRoot() { return root; } //insert a new value into the heap // void insert(int value, heapNode newNode) //{ // if(counter == 0) // { // newNode = new heapNode(value); // root = newNode; // } // else // { // insertSpot(counter); // newNode = new heapNode(value); // } //while(newNode.getValue() != root.getValue()) //{ //if(newNode > parent) //break; //elseif(newNode < parent) //counter-1 node.setValue(newNode.getValue()); // } // counter++; // } / int delete(rootValue) { heapNode tempNode = new heapNode(value, left, right) go down the heap to the last one make it root last nodeValue = null while(not at the bottom level of tree) { if(newRoot < left) break; elseif(newRoot > left) swap with left; } return tempNode; } / }; // end of heap class int main() { heap *myHeap; myHeap = new heap(); int option=9; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); } myHeap->print(); return 0; }

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Apr 1st, 2006, 5:00 PM	#41
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 333 Rep Power: 4	i don't know. A min heap just fills them up left to right. I was told if you take the number of times something has been entered like keep a counter. Like if you enter the numbers 12, 14, 19 the counter would be 3 because 3 numbers have been entered. Then if you take the binary representation of that counter number it tells you where the next one should go. You put the binary numbers into an array and then look at each 1 or 0 ignoring the most significant 1. And then if the next number in the array is 1 move right if its 0 move left. Then when the numbers done wherever it is thats where the new value goes. Then you compare that value to the parents and swap accordingly. Is there a different easier way to keep track of the insert spot? I really need help because this has to be done by tuesday and i do not even have the insert done.

Apr 1st, 2006, 6:16 PM	#44
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 333 Rep Power: 4	like you take the counter and mod it by 2 and then devide the counter by 2 and mod the new counter and then keep going until the counter is 0 and then you take each of those mod 2 numbers which each will be a 0 or 1 and put them into an array. Then you ignore the most significant 1 and all 0 before it and take the rest of the 1 and 0 s and they tell you which way to go to insert the next value

Apr 1st, 2006, 7:26 PM	#46
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 333 Rep Power: 4	im using emacs editor on a unix server. I do not really know completely how to use it. Thanks for all the suggestions ill make the changes and see what happens

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

pointer help