Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

So on the outside, the access is by key only? Then the order doesn't matter at all. It's just your way of looking at the weighting of your items, but that's all your task calls for — not an order, but a way to weight elements. Your single constraint is that there needs to be a fast way to locate the item with the lowest (or highest, depending which way around you want to define it) weight.

Well, that is indeed what a heap is good for. A heap is a complete binary tree with a simple condition: the parent's value is always greater than either of its childrens' values. That means the greatest value of the tree is always at its root. Leaves only exist at the very bottom of the tree. To insert an element, you attach it to a free slot of any of the leaves. In that case, or if you adjust a child's value such that it violates this requirement, the violation is trivial to fix: you swap it with its parent, which may recursively cause a new violation with regard to its new parent. Since the structure is always a complete binary tree and you have to do this for any operation (either up the tree or down the tree depending on whether you are inserting or removing elements), all operations happen in O( log n ).

This is obviously faster than your linear-time splices.

And there is more excellent news for you: since a heap is a complete binary tree, it's easy to map to an array. Just define the children of the element at position i to be the elements at 2i and 2i + 1. Obviously, the parent of an element is int( i / 2 ). That's for a 1-based index, for 0-based index, you need some additions and subtractions to twiddle the numbers appropriately. The tree root is then at 1, its children are at 2 and 3, their respective children are at 4, 5 and 6, 7, the next level of siblings is at 8 - 15, etc.

In your case, I'd store your actual data in a hash as one would normally do. I'd use an array-as-heap to store hash keys, and another hash to be able to map keys to heap locations. That mapping is bidirectional, so you don't need any linear scans. If you need to remember explicit weights, it's cheapest to do that using another $key => $weight hash — that way you avoid having zillions of tiny anonymous data structures, and keeping two or three hashes with identical key sets in synch is a no-brainer anyway.

If that was too short and you haven't read Sedgewick's "Algorithms", get it. Actually, if you haven't read it, get it, regardless of whether the above was sufficient. It's a classic and a staple of CS for good reason.

Makeshifts last the longest.


In reply to Re^3: Re-orderable keyed access structure? by Aristotle
in thread Re-orderable keyed access structure? by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others contemplating the Monastery: (7)
    As of 2020-02-18 10:51 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      What numbers are you going to focus on primarily in 2020?










      Results (75 votes). Check out past polls.

      Notices?