in reply to Heap structure for lookup?

I'd look at using a B-tree for this type of problem, lookups are efficient once the tree is created. Balancing the tree when adding or removing elements can be somewhat expensive, but b-trees don't need to be balancing as frequently as binary trees so it's not too bad. Many databases use b-trees -- but you seem to be ruling those out for some reason ;)

Replies are listed 'Best First'.
Re^2: Heap structure for lookup?
by BrowserUk (Patriarch) on May 27, 2015 at 09:49 UTC

    They certainly reduce the infrastructure overhead (number of pointers), but the last time I used b-tree was ~20 years ago, and my memory of them is ***AAAAAAAAAAAAARGGGG!***.

    We were using a library purchased from a 3rd party company that went to the wall and needed to move from 16 to 32-bit compiles.

    We had the source code and thought it would be reasonably easy, till we looked. It was a nightmare. The algorithms are really quite involved.

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
    In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]

      As you're only storing single values it shouldn't be too bad, only the balancing code gets a bit involved, when you split the current node you insert into it's parent node which may cause it to split and so on back up to the root node. It's really not that hard, once you get your head round it.

      Anyway you've had 20 more years of experience since then, so you shouldn't have any problems ;)

[reply]
        Anyway you've had 20 more years of experience since then, so you shouldn't have any problems

        If only it worked that way. If only :)

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
        In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]

In Section Seekers of Perl Wisdom