Thread: Heap?

  1. #1
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489

    Heap?

    Does heap memory that they said in programming discussion is:
    http://en.wikipedia.org/wiki/Heap_(data_structure)

    And also stack in _alloca?
    http://en.wikipedia.org/wiki/Stack_(data_structure)
    Just GET it OFF out my mind!!

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    No that is a heap datastructure, and has nothing (directly) to do with Heap memory.

    Heap memory is just a chunk (or even multiple chunks) of memory that is given to the application - malloc or new then carves this up into smaller sections that are given back to the application for it's use. You can make a "simple heap" by just declaring a large array and then letting your own version of alloc return some part of the array, and free will allow the passed in part of array to be reused.

    And the stack is not the same either.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    Do you know what is the meaning of "Θ(lg n) or Θ(1)"?

    I don't understand what are they wrote on the page with those symbols...
    Just GET it OFF out my mind!!

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by audinue
    I don't understand what are they wrote on the page with those symbols...
    Before presenting the table that uses symbols which you do not understand, that article links to another article on computational complexity. Read that other article.

    EDIT:
    okay, but you will have to follow yet another link to an article on "Big O" notation.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    At Comparison of theoretic bounds for variants in Heap(data structure)

    Θ(lg n) or Θ(1)?

    Θ == speed/memory/something?
    lg == log?
    n == ?
    Just GET it OFF out my mind!!

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by audinue View Post
    At Comparison of theoretic bounds for variants in Heap(data structure)

    Θ(lg n) or Θ(1)?

    Θ == speed/memory/something?
    lg == log?
    n == ?

    Big-O notation indicate "the number of operations". n is "the number of items". lg n certainly means log(n). O(1) means "one operation" - for example, adding an element to the end of a linked list is O(1) if you have a pointer to the end you are adding at. If you have to walk the linked list, it becomes O(n). A binary search in an array is O(log2(n)).
    Simple forms of sorting (which consist of two nested for-loops) are O(n^2).

    Note however that this is just a "overall efficency" number - so you can't directly compare it. For example, if we store hash-values of strings in an array (sorted in hash-order), and compare it to a binary search in a straightforward array of strings, the O number will be the same. But comparing (long) strings is much slower than comparing a single integer.

    So O numbers are really only "an indication of what happens when n grows" - do if you double the number of items, does it take twice as long, a tiny bit longer or MUCH longer.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    And yes, lg == log2. It looks like you've got Θ, which is Big-Theta notation. Big O is just an upper bound; Big Theta is both an upper bound and a lower bound (meaning it's right on).

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by tabstop View Post
    And yes, lg == log2. It looks like you've got Θ, which is Big-Theta notation. Big O is just an upper bound; Big Theta is both an upper bound and a lower bound (meaning it's right on).
    So Big-Theta says "It always takes this long", but Big O is "It could take this long, but also less time" - I learned something new today too!

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    As I understand it, if we can say "It always takes this long," then we have a procedure that takes place in constant time. You are correct in that a stricter notation will establish guarantees, but wikipedia says this about the matter:

    Quote Originally Posted by wiki
    Infinite asymptotics

    Big O notation is useful when analyzing algorithms for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size n might be found to be T(n) = 4n² − 2n + 2.

    As n grows large, the n² term will come to dominate, so that all other terms can be neglected — for instance when n = 500, the term 4n² is 1000 times as large as the 2n term. Ignoring the latter would have negligible effect on the expression's value for most purposes.
    There is also no guarantee about "it could take this long". Such a guarantee is an upper bound. Perhaps, "we've never seen anything perform worse before". That's probably not right either but Big O really offers nary a guarantee except how the work will scale with n.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. heap
    By George2 in forum Windows Programming
    Replies: 2
    Last Post: 11-10-2007, 11:49 PM
  2. Heap Work
    By AndyBomstad in forum C++ Programming
    Replies: 1
    Last Post: 05-16-2005, 12:09 PM
  3. Do you know...
    By davejigsaw in forum C++ Programming
    Replies: 1
    Last Post: 05-10-2005, 10:33 AM
  4. heap question
    By mackol in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 05:03 AM
  5. stach and heap.
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 01-26-2002, 09:37 AM