[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Stack vs. heap?
David4602@gmail.com wrote:
Michael Black wrote:
And isn't a heap something that comes and goes?
Yes, definitely. In higher level languages, heaps come and go as code
that requires it comes into and goes out of scope.
Ie, you need some storage, it gets allocated, and then
the memory is returned to free memory after
it's not being used.
Yes.
This is different from variables that remain forever, such as the system
variables that use up the zero-page.
Global variables are different than the heap - or perhaps global
variables are the first heap that doesn't go out of scope until the
program ends. (I'm not talking about 6502 programming specifically
here, I'm talking about more generic high-level language
implementations.)
Actually, data structures allocated on "the heap" are potentially
global to the program that allocates them (dependent on language
restrictions).
Static variables are allocated once, when a program is initiated,
and persist for the life of the program.
Heap variables are allocated on demand, and persist until they
are either explicitly freed or until they are "garbage collected"
because they are no longer in use.
Local (or stack) variables are allocated each time a procedure is
called, and persist until it exits that call.
An OS may support objects of even greater scope (persistence) than
a program, such as environment variables, queues, or files.
And, as Matt has noted, there is a specific data structure called
a "heap", that is a partially-ordered tree. This data structure
is very useful for efficient sorting, since an item can be added
or removed in at most log(n) operations. Its first appearance was
in the "heapsort" algorithm, in which the binary tree is mapped
onto an array of elements, without explicit links. This allowed
an order N*log(N) sort to be written without requiring any more
storage than the data itself (unity storage ratio).
-michael
Parallel computing for 8-bit Apple II's!
Home page: http://members.aol.com/MJMahon/
"The wastebasket is our most important design
tool--and it is seriously underused."