Binary heap "tie breaking" question
in [General Programming]
|
From: mike3 on 10 Feb 2010 00:19 Hi. 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)?
From: Rod Pemberton on 10 Feb 2010 03:49 "mike3" <mike4ty4(a)yahoo.com> wrote in message news:67af2c15-e71a-4926-bc8f-69ac6d8a7339(a)o28g2000yqh.googlegroups.com... > > 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)? If you have "multiple objects with the same 'key'", then you have a hash collision: http://en.wikipedia.org/wiki/Hash_collision If you know the key collides, then you perform secondary comparisons to determine which data to access. You should do so anyway since you can't eliminate the possibility of a collision. As for "enforcing a consistent LIFO or FIFO behavior", I don't know what you're asking about. Rod Pemberton
From: mike3 on 10 Feb 2010 05:53 On Feb 10, 1:49 am, "Rod Pemberton" <do_not_h...(a)havenone.cmm> wrote: > "mike3" <mike4...(a)yahoo.com> wrote in message > > news:67af2c15-e71a-4926-bc8f-69ac6d8a7339(a)o28g2000yqh.googlegroups.com... > > > > > 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)? > > If you have "multiple objects with the same 'key'", then you have a hash > collision:http://en.wikipedia.org/wiki/Hash_collision > This isn't a "hash", it's the values the heap is "heaped" by (e.g. if we were doing a priority queue, this would be the priority value). If "key" isn't the right term, what is? > If you know the key collides, then you perform secondary comparisons to > determine which data to access. You should do so anyway since you can't > eliminate the possibility of a collision. > > As for "enforcing a consistent LIFO or FIFO behavior", I don't know what > you're asking about. > That means if we push on multiple objects to the heap with the same "key", then when we pop them off they're guaranteed to come off in one of those two orders (which one is set when we set up the heap).
From: Moi on 10 Feb 2010 07:55 On Tue, 09 Feb 2010 21:19:34 -0800, mike3 wrote: > Hi. > > 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)? (If I understood your problem correctly, don't know if your heap can be viewed as a BT) Rotations in binary trees preserve order iff you don't rotate on equal keys. HTH AvK
From: Richard Harter on 10 Feb 2010 11:29
On Tue, 9 Feb 2010 21:19:34 -0800 (PST), mike3 <mike4ty4(a)yahoo.com> wrote: >Hi. > >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. If this won't work there is a data structure that I call a heap structured heap tree. (I may have invented it - I can't find any references.) A binary tree is a heap structure search tree if Definition: A min heap structured search tree (min HSST) is a binary tree with the following properties: 1. For each node all elements in the left subtree are less than the elements in the right subtree. 2. The parent node is less than any of its children. Adopting the convention that a newly inserted element is greater that existing elements with the same key gives your heap. There is an article that describes them: http://home.tiac.net/~cri/2008/traversal.html The article is incorrect about performing rotations. It is true that they cannot be done in the same way as in binary search trees but there is an equivalent operation. HTH 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. |