Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Apr 1st, 2006, 10:26 AM   #31
nnxion
Programming Guru
 
nnxion's Avatar
 
Join Date: Jun 2005
Location: elemental plane
Posts: 1,429
Rep Power: 5 nnxion is on a distinguished road
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;
}
You may find it easier to work with arrays instead, plenty examples on google for that.
__________________
"Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for."
-- Socrates
nnxion is offline   Reply With Quote
Old Apr 1st, 2006, 4:04 PM   #32
cwl157
Professional Programmer
 
Join Date: Feb 2005
Posts: 327
Rep Power: 4 cwl157 is on a distinguished road
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.
cwl157 is offline   Reply With Quote
Old Apr 1st, 2006, 4:12 PM   #33
nnxion
Programming Guru
 
nnxion's Avatar
 
Join Date: Jun 2005
Location: elemental plane
Posts: 1,429
Rep Power: 5 nnxion is on a distinguished road
Quote:
Originally Posted by cwl157
i can not use arrays i have to use nodes and a tree because it has to handle 1 billion entries.
LOL 1 billion? You think a tree using objects can, but an array can't?
__________________
"Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for."
-- Socrates
nnxion is offline   Reply With Quote
Old Apr 1st, 2006, 4:23 PM   #34
grumpy
Programming Guru
 
grumpy's Avatar
 
Join Date: Jun 2005
Location: Adelaide, South Australia
Posts: 1,198
Rep Power: 5 grumpy is on a distinguished road
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.
grumpy is offline   Reply With Quote
Old Apr 1st, 2006, 4:24 PM   #35
cwl157
Professional Programmer
 
Join Date: Feb 2005
Posts: 327
Rep Power: 4 cwl157 is on a distinguished road
i dont know thats just what i was told
cwl157 is offline   Reply With Quote
Old Apr 1st, 2006, 4:26 PM   #36
DaWei
Resident Grouch
 
DaWei's Avatar
 
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10 DaWei is on a distinguished road
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
DaWei is offline   Reply With Quote
Old Apr 1st, 2006, 4:26 PM   #37
grumpy
Programming Guru
 
grumpy's Avatar
 
Join Date: Jun 2005
Location: Adelaide, South Australia
Posts: 1,198
Rep Power: 5 grumpy is on a distinguished road
What you were told is wrong, cwl..
grumpy is offline   Reply With Quote
Old Apr 1st, 2006, 4:31 PM   #38
grumpy
Programming Guru
 
grumpy's Avatar
 
Join Date: Jun 2005
Location: Adelaide, South Australia
Posts: 1,198
Rep Power: 5 grumpy is on a distinguished road
Quote:
Originally Posted by DaWei
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.
Not necessarily. I've lost count of the number of times I've seen designs that involve keeping several million objects in memory are proposed as the "obvious" solution, when (in fact) smarter schemes to extract objects from mass storage when needed actually make more sense. All because the designer can't be bothered nutting out a smarter access scheme.
grumpy is offline   Reply With Quote
Old Apr 1st, 2006, 4:35 PM   #39
cwl157
Professional Programmer
 
Join Date: Feb 2005
Posts: 327
Rep Power: 4 cwl157 is on a distinguished road
so how does that insert fit in with the insertSpot method that tells me where the next value goes?
cwl157 is offline   Reply With Quote
Old Apr 1st, 2006, 4:47 PM   #40
The Dark
Expert Programmer
 
Join Date: Jun 2005
Posts: 816
Rep Power: 4 The Dark is on a distinguished road
Quote:
Originally Posted by cwl157
so how does that insert fit in with the insertSpot method that tells me where the next value goes?
I don't know that anyone will be able to tell you that, as no one except you knows what that function is supposed to do. It doesn't fit in with normal min-heap processing as it doesn't attempt to compare the new value with what is already in the heap.
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.
The Dark is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

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

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 3:13 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC