![]() |
|
![]() |
|
|
Thread Tools | Display Modes |
|
|
#31 |
|
Programming Guru
![]() Join Date: Jun 2005
Location: elemental plane
Posts: 1,429
Rep Power: 5
![]() |
Still plenty to do, but here is a bit of code, that will get you started:
// TODO: modify it so it doesn't always insert into left,
// but traverses up when size is a certain value
// and swaps the values when one is bigger than it's parent
bool insert(int value)
{
static heapNode * last = NULL;
// make a new heapNode and set the value
heapNode *newNode = new heapNode(value);
// you can make it so the heap constructor sets root to last
if(last == NULL)
last = root;
// check left child
if(last->getLeft() == NULL)
{
// check here to see if parent is bigger than child, if so swap
last->setLeft(newNode);
}
// check right child
else if(last->getRight() == NULL)
{
// check here to see if parent is bigger than child, if so swap
last->setRight(newNode);
}
// both children are filled, so either traverse/percolate up or make one of the children your new last
// depending on how well balanced the heap is
else
;
// TODO: set last to the last node or parent
// increment size
size++;
return true;
}
__________________
"Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates |
|
|
|
|
|
#32 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 327
Rep Power: 4
![]() |
i can not use arrays i have to use nodes and a tree because it has to handle 1 billion entries. also this insert method goes in the heap class right? also, how does this relate to the insertSpot method with the counter that tells where the next value goes?
Last edited by cwl157; Apr 1st, 2006 at 4:22 PM. |
|
|
|
|
|
#33 | |
|
Programming Guru
![]() Join Date: Jun 2005
Location: elemental plane
Posts: 1,429
Rep Power: 5
![]() |
Quote:
__________________
"Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates |
|
|
|
|
|
|
#34 |
|
Programming Guru
![]() Join Date: Jun 2005
Location: Adelaide, South Australia
Posts: 1,198
Rep Power: 5
![]() |
Indeed. You're more likely to run out of memory building the tree with 1B nodes than you are to run out of memory using an array with 1B elements, as the combination of nodes and the objects will be larger than an object.
The only potential exception is when memory is fragmented, and it is difficult to dynamically allocate a very large contiguous array. A more usual reason for using a linked list and not an array is because insertions into the middle of the list are faster. It is certainly not done to save memory, or to support larger sets of objects. The more usual reason to use an array (apart from the fact it's contiguous) is that, once the elements are in the array, accessing them in random order is faster. |
|
|
|
|
|
#35 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 327
Rep Power: 4
![]() |
i dont know thats just what i was told
|
|
|
|
|
|
#36 |
|
Resident Grouch
![]() ![]() ![]() ![]() ![]() ![]() Join Date: Jun 2005
Posts: 6,453
Rep Power: 10
![]() |
An simple array uses less storage because the pointer is implicit in the index. A gig of entries is probably going to live in mass storage, which reduces the concern over precise in-memory method, anyway.
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers |
|
|
|
|
|
#37 |
|
Programming Guru
![]() Join Date: Jun 2005
Location: Adelaide, South Australia
Posts: 1,198
Rep Power: 5
![]() |
What you were told is wrong, cwl..
|
|
|
|
|
|
#38 | |
|
Programming Guru
![]() Join Date: Jun 2005
Location: Adelaide, South Australia
Posts: 1,198
Rep Power: 5
![]() |
Quote:
|
|
|
|
|
|
|
#39 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 327
Rep Power: 4
![]() |
so how does that insert fit in with the insertSpot method that tells me where the next value goes?
|
|
|
|
|
|
#40 | |
|
Expert Programmer
Join Date: Jun 2005
Posts: 816
Rep Power: 4
![]() |
Quote:
For example, do you have to create all the intermediate nodes in your heap when you are trying to get to the right "spot", obviously they have to exist, but what value should they have? As this is your design, and you don't seem to want to change it, you need to work out what to do. |
|
|
|
|
![]() |
| Bookmarks |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
| Thread Tools | |
| Display Modes | |
|
|