Binary heap "tie breaking" question
in [General Programming]
|
From: mike3 on 11 Feb 2010 15:17 On Feb 11, 12:21 pm, Alex Fraser <m...(a)privacy.net> wrote: > On 11/02/2010 17:14, Richard Harter wrote: > > > > > On Wed, 10 Feb 2010 21:07:21 +0000, Alex Fraser<m...(a)privacy.net> > > wrote: > >> On 10/02/2010 16:29, Richard Harter wrote: > >>> On Tue, 9 Feb 2010 21:19:34 -0800 (PST), mike3 > >>> <mike4...(a)yahoo.com> wrote: > >>>> I was wondering: Suppose we use a binary heap to keep a list of > >>>> objects sorted by associated "keys". How can one enforce a consistent > >>>> LIFO or FIFO behavior of this when dealing with multiple objects with > >>>> the same "key" (i.e. tie breaking)? > > >>> The obvious and simple way to do this is to add a field that has > >>> the entry index, i.e., the first item entered has index 1, the > >>> second index 2, and so on. The index is your tie breaker. > > >> I'd recommend this, though a 32-bit counter could easily be exhausted > >> during a run of a program. An unsigned 64-bit one should outlast the > >> software - I make it over 500 years at a billion insertions per second.. > [snip] > > What you can do is check for counter overflow and reassign the > > existing count fields when there is an overflow. THe cost of > > this is nominal. > > Sorry if I'm being dense, but I'm not sure what you mean. Please can you > explain? > > >> All the alternatives seem likely to have similar or greater space > >> overhead, equal or worse time complexity, and greater code complexity. > > > Agreed. > > >>> If this won't work [...] > > >> Am I missing a situation where it won't, or are you just not sure there > >> aren't any? > > > "Won't work" means not a solution given the constraints. We > > don't know what the constraints are but the OP does. Frex he > > might not want to provide space for a count field. > > The applicable set of constraints is what I meant by "situation". The > only relevant constraint I could (and still the only one I can) think of > was the additional space due to the count field, but per the comment > from my previous post, if that is the case then there may be no solution > without sacrificing time complexity. > I was thinking of using this for two things: first, for the A* pathfinding algorithm, which keeps a list sorted according to a cost score (this is what the heap is used for), and it needs to handle ties, and second, there's also a priority queue with events in it. Now I might be able to reserve room for a counter, though I'll have to see. Does using the counter (sacrificing some space) preserve time complexity? Also, what are the details of how to implement the counter method? E.g. does the counter just work as an additional comparison point that is switched over to when the key compares equal (i.e. if the key is equal, then we compare counters to resolve the tie)? If so, how does one choose which of LIFO or FIFO behavior is wanted? Just change the counter compare (> vs <)?
From: Richard Harter on 11 Feb 2010 15:42 On Thu, 11 Feb 2010 19:21:24 +0000, Alex Fraser <me(a)privacy.net> wrote: >On 11/02/2010 17:14, Richard Harter wrote: >> On Wed, 10 Feb 2010 21:07:21 +0000, Alex Fraser<me(a)privacy.net> >> wrote: >>> On 10/02/2010 16:29, Richard Harter wrote: >>>> On Tue, 9 Feb 2010 21:19:34 -0800 (PST), mike3 >>>> <mike4ty4(a)yahoo.com> wrote: >>>>> I was wondering: Suppose we use a binary heap to keep a list of >>>>> objects sorted by associated "keys". How can one enforce a consistent >>>>> LIFO or FIFO behavior of this when dealing with multiple objects with >>>>> the same "key" (i.e. tie breaking)? >>>> >>>> The obvious and simple way to do this is to add a field that has >>>> the entry index, i.e., the first item entered has index 1, the >>>> second index 2, and so on. The index is your tie breaker. >>> >>> I'd recommend this, though a 32-bit counter could easily be exhausted >>> during a run of a program. An unsigned 64-bit one should outlast the >>> software - I make it over 500 years at a billion insertions per second. >[snip] >> What you can do is check for counter overflow and reassign the >> existing count fields when there is an overflow. THe cost of >> this is nominal. > >Sorry if I'm being dense, but I'm not sure what you mean. Please can you >explain? My apologies. The underlying assumption is that n, the number of elements in the heap, is small relative to N, the maximum size of the counter. If it is not a larger counter is needed. When a record is inserted the counter is incremented and checked for overflow. If it is about to overflow we reassign the counter fields. One way to do this is to stablely convert the heap to a HSST. This can be done in O(n*log(n)) time without extra storage. Now traverse the heap and assign indices {0...n-1} to the count fields; the order doesn't matter. If n*log(n)<N the amortized time cost is O(1). There probably is a more efficient way than doing the HSST conversion, but that is enough for a proof of principle. > >>> All the alternatives seem likely to have similar or greater space >>> overhead, equal or worse time complexity, and greater code complexity. >> >> Agreed. >> >>>> If this won't work [...] >>> >>> Am I missing a situation where it won't, or are you just not sure there >>> aren't any? >> >> "Won't work" means not a solution given the constraints. We >> don't know what the constraints are but the OP does. Frex he >> might not want to provide space for a count field. > >The applicable set of constraints is what I meant by "situation". The >only relevant constraint I could (and still the only one I can) think of >was the additional space due to the count field, but per the comment >from my previous post, if that is the case then there may be no solution >without sacrificing time complexity. I think more qualifiers are needed. We don't need a count field if the heap is maintained in a binary tree. If it is being maintained in an array we have to specify how much extra storage is permitted. It may be that log(n) or sqrt(n) storage may suffice for retaining the same time complexity. That said, using an HSST will have log(n) complexity per insert/delete with O(1) additional space. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Infinity is one of those things that keep philosophers busy when they could be more profitably spending their time weeding their garden.
From: mike3 on 11 Feb 2010 22:08 On Feb 11, 1:42 pm, c...(a)tiac.net (Richard Harter) wrote: <snip> > I think more qualifiers are needed. We don't need a count field > if the heap is maintained in a binary tree. If it is being > maintained in an array we have to specify how much extra storage > is permitted. It may be that log(n) or sqrt(n) storage may > suffice for retaining the same time complexity. > In this case it's being done with the array (tree-as-array thingy, not sure what it's called). How would you do this with log(n) or sqrt(n) additional storage?
From: Richard Harter on 14 Feb 2010 12:48
On Thu, 11 Feb 2010 18:14:46 GMT, cri(a)tiac.net (Richard Harter) wrote: >On Thu, 11 Feb 2010 02:57:40 -0800 (PST), Calum ><calum74(a)googlemail.com> wrote: > >>On Feb 10, 4:29=A0pm, c...(a)tiac.net (Richard Harter) wrote: >>> On Tue, 9 Feb 2010 21:19:34 -0800 (PST), mike3 >[snip description] > >>> There is an article that describes them:http://home.tiac.net/~cri/2008/tr= >>aversal.html >> >>I think the crucial issue is whether the heap is stored in a binary >>tree or in an array. I would by default assume that heaps are stored >>in arrays. >> >>The problem as I see it with your min HSST is that they can't be >>stored in arrays efficiently, as inserting an element into the heap is >>O(n), not O(ln n) > >But that isn't true. Insertion into an HSST in an array can be >done in O(ln n) time. The algorithms are similar to sifting up >and sifting down. Sniff. Calum is correct. Sifting up in array can be done in O(log n) time. However sifting down is an O(n) operation. So much for a new inplace stable sort. |