🔒 Locked

Priority Queue Searching - heaps

Started by Mithrandir Jan 30, 2006 at 9:51 AM 11 replies 2.5k views

Original Post

235

Jan 30, 2006 at 9:51 AM

I've got a system where I need rapid insertions and deletions of timed events, and I need to be able to quickly pull the event with the lowest time off the queue. I've been using heaps for years now, and they are incredibly efficient for this purpose, and seem like an almost perfect solution, except when it comes to one thing: searching. Here's the problem; I've decided that I need the ability to pause these timed events, which means readjusting their execution time. Unfortunately, when you change the value that items are sorted by in a heap, it is no longer garanteed to be a heap, and the item must be moved around in order to reheapify the structure. This in itself isn't a huge problem; I've determined that all I need to do is walk the changed value up if it's value increased, or walk it down if its value decreased, and the heap property will become true again, giving a very nice O(log n) algorithm. The real problem, however, is searching for that item to change in the first place. If I pause one of these timed events, I can't walk it up or down if I don't know where it is in the heap, right? So I need to first find it... which is an O(n) algorithm, and it completely destroys the nice performance I was getting. Furthermore, since items inside a heap aren't garanteed to be in a particular spot (they can move up and down whenever a new item is inserted or removed), I can't store the index of the item anywhere, because it can change at any time (I'm using a packed binary-tree stored in an array). The only fast way I can think of to solve this is to actually store an items index inside the item itself whenever the heap moves it around, but this has design and performance rammifications. I don't like it when data containers modify their contents, it just doesn't seem like it's a right thing to do; and furthermore, I'm introducing memory and cpu overhead by storing indexes of items. There is one other solution I pondered, but that turned out to be a complete disaster when I tested it out. We know that one property always remains true in a heap: every subnode of any given node will have a value less than the node. So, if I perform a tree search starting at the root, I can cut out every subtree that has a value less than the value I'm looking for. While this seems to be a good idea in theory, in practice it sucked. First of all, the overhead of performing a recursive search (or an iterative search utilizing a stack or a queue) was incredibly high, and killed performance. Second of all, the algorithm is still O(n) because in a worst case scenario, it will still search every node in the tree. Thirdly, the heap insertion algorithm is pretty good, and almost always ends up creating well balanced trees, so in reality, not very many subtrees are ever eliminated from consideration anyways. In my test harness, searching for 500 items in a 5,000,000 node tree took 1 minute 6 seconds using the "smart" algorithm. It took 2.5 seconds using a simple iterative array search for the same exact search. So... the question is; is there any algorithmic way of searching for a particular item in a heap that gives performance better than O(n)? I'm not seeing any.

Mithrandir

Author

235

Mithrandir

Jan 31, 2006 at 9:20 AM

No takers?

well damn.

KulSeran

196

KulSeran

Jan 31, 2006 at 10:38 PM

How important is it to get everything out in the proper order?
Can you wait to reheapify an item untill it bubbles to the top of the heap?

If not, then i think the best way is the position flag inside each node.
If you had your nodes in the heap made of something like pseudo code:

class Event{... OnPauseCallBack() { dostuff(); mynode::OnChange(); }}class node{int pos;Event *event; // Or use templates to make this "node" more flexable for other usesOnChange() { reheapifyme(); }};

When an event changes states, it can call it's parent node's reheapify member.
BUT this does incur at the minimum the position flag worth of overhead. But the data container is NOT chaning its contence. It is changing its node's contence.
The only dificulty is making a callback system that works for you, so that a node knows that it needs to fix it's position.

You seem to be VERY concerned about memory and speed. Is this for a realtime or embedded app?

Mithrandir

Author

235

Mithrandir

Feb 1, 2006 at 7:56 AM

Quote:
Original post by KulSeran
How important is it to get everything out in the proper order?
Can you wait to reheapify an item untill it bubbles to the top of the heap?

If not, then i think the best way is the position flag inside each node.
If you had your nodes in the heap made of something like pseudo code:
*** Source Snippet Removed ***

When an event changes states, it can call it's parent node's reheapify member.
BUT this does incur at the minimum the position flag worth of overhead. But the data container is NOT chaning its contence. It is changing its node's contence.
The only dificulty is making a callback system that works for you, so that a node knows that it needs to fix it's position.

You seem to be VERY concerned about memory and speed. Is this for a realtime or embedded app?

It's for a realtime server application.

After further consideration, I don't think that pausing these timers will occur very often, and it may be acceptable to use an O(n) solution. I'll have to wait until I get the system running to see how it actually affects performance though.

Iftah

Feb 1, 2006 at 8:43 AM

Im sure you thought about it, but still - considered using a fully ordered tree?

like red-black or AVL (or STL's map/set)

this will give O(logn) operations if I remember correct

while this is slower than the heap's O(1) pop, its still not too bad (log is extreemly slow growing function), for example for 5 million items it can be just 10-30 iterations to pop/find/insert

Iftah.

Trap

Feb 1, 2006 at 8:58 AM

You need a decreaseKey(itemhandle,newkey) function for any shortest path search algorithm, with a google for decreasekey you get a lot of page-hits, probably some also have implementation notes.

I have written 2 or 3 different heaps that support decreaseKey. It's quite simple: You need 1 or 2 additional tables to manage the itemhandle <-> priority queue entry associations which is a bit of overhead, but it's not too bad (in Java it's still way faster than the java.util.PriorityQueue...).

With radix heaps it's way easier: Every queue entry already is a distinct object, so you can return a pointer to the queue entry as your itemhandle. Changing the priority of an entry is as simple as 1 double-linked-list unlinking and 1 list prepending.

Mithrandir

Author

235

Mithrandir

Feb 1, 2006 at 9:44 AM

Quote:
Original post by Iftah
Im sure you thought about it, but still - considered using a fully ordered tree?

like red-black or AVL (or STL's map/set)

this will give O(logn) operations if I remember correct

while this is slower than the heap's O(1) pop, its still not too bad (log is extreemly slow growing function), for example for 5 million items it can be just 10-30 iterations to pop/find/insert

Iftah.

The original reason I decided on a heap is that it can easily be stored into an array, since it's packed.

IIRC, RBT's and AVL's (I'd use RBT's) don't pack the tree, and thus need to be stored in some kind of memory-allocating system, unless I develop some kind of node pool. I'm not sure I want to go with that much effort right now, but I guess it's something to think about.

Heaps:
fast O(logn) insertions and removals
fast O(logn) reorderings
slow O(n) searches
O(1) access to the first element

RBT's:
slow O(logn) insertions and removals (slow due to the node management)
slow O(logn) reorderings (requires a removal and reinsertion IIRC?, essentially doubling the time)
O(logn) access to the first element, unless I write a wrapper around it to keep track of this automatically.
fast O(logn) searches.

*ponder*

Mithrandir

Author

235

Mithrandir

Feb 1, 2006 at 3:23 PM

Also, after spending all day trying to figure out why my RBT implementation in .NET doesn't work, I just figured out that the RBT rotation algorithms pretty much break any RBT that contains duplicate keys.

Unfortunately, duplicate keys are a requirement for me, and the only way I can think of to make it work is to use a bucket in each node for identical keys, which introduces even more overhead than I would like.

Mithrandir

Author

235

Mithrandir

Feb 1, 2006 at 3:25 PM

Oh man...

I just ran a test harness with 10,000,000 data entries...

Heap wins, hands down.

RBT took 2 minutes and 0.93 seconds.

Heap took 8.70 seconds.

I'm sorry, but that kind of overhead is unacceptable, RBT's are out of the question.

Iftah

Feb 1, 2006 at 6:53 PM

ouch, sorry for the bad advice [sad]

Im rusty on data structures, but surely you dont need to re-heapify if one node changes. You can sift it up/down to a new proper place.
To find it fast (O(1)) I guess you must keep a handle to its place in the heap. Since it can move around this is problematic, I see two easy solutions:

1) The heap keeps refrence to each items handle and when the item moves around the heap updates the handle.

2) you dont keep the heap as a packed array but as a tree (with pointers to chlidren nodes and parent and such). The "handle" the item keeps is simply the pointer to its address. When you need to move the item in the heap you dont move it in the memory at all (so anyone pointing to it will stay valid) but instead you change its sons/parent pointers. This is O(1) work but kinda ugly bug prone code (lots of special cases).

for example:

say B has parent A and children C and D,and F has E parent and G,H children:       A            E      /            /     B            F    / \          / \       C   D        G   Hyou want to switch B and F in the heap without moving them in the memory (so pointers to them will stay valid) so you change B's children to be G and H,B's parent to be E, F's parent to be A, F's children to be C and D.A's left son is set to F,  E's left son is set to BC and D's parent are set to F,  G and H parent are set to Bthere are special cases such as B is parent of F,  B is child of F, C is nil, A is nil, etc...

PS. its possible option 2 is less cache friendly so may result in slower code (espcially if your heap doesnt fit in the cache, which I understand is the situation).
Im guessing this is why RBT was so bad compared to the heap. Not because its O(logn) instead of O(1) (as logn is so small), but because lots more cache misses caused the CPU to wait for data from memory. Did you profile the code for cache performance?

Iftah.
[/source]

[Edited by - Iftah on February 2, 2006 7:53:20 AM]

Mithrandir

Author

235

Mithrandir

Feb 2, 2006 at 7:39 AM

Quote:
Original post by Iftah
ouch, sorry for the bad advice [sad]

Oh no, don't misunderstand, it wasn't bad advice. When I used C++, RBT's were the best way to go for most things, and I'm surprised I didn't think of it as a possible solution.

Quote:

Im rusty on data structures, but surely you dont need to re-heapify if one node changes. You can sift it up/down to a new proper place.

when I said "re-heapify", I meant an O(logn) algorithm that either walks the changed node up or down, depending on its new value. This is perfectly acceptable and I already have an algorithm that works for this purpose.

Quote:

To find it fast (O(1)) I guess you must keep a handle to its place in the heap. Since it can move around this is problematic, I see two easy solutions:

1) The heap keeps refrence to each items handle and when the item moves around the heap updates the handle.

This is the most efficient way I can think of, but I'm not sure I want to take the step to go this far yet, because it would require that the collection change the data that it stores. I'll wait until I get the system running to see if my problem is a real problem or not.

Quote:

2) you dont keep the heap as a packed array but as a tree (with pointers to chlidren nodes and parent and such). The "handle" the item keeps is simply the pointer to its address. When you need to move the item in the heap you dont move it in the memory at all (so anyone pointing to it will stay valid) but instead you change its sons/parent pointers. This is O(1) work but kinda ugly bug prone code (lots of special cases).

I'm using managed C#, pointers are out of the question :)

Quote:

PS. its possible option 2 is less cache friendly so may result in slower code (espcially if your heap doesnt fit in the cache, which I understand is the situation).
Im guessing this is why RBT was so bad compared to the heap. Not because its O(logn) instead of O(1) (as logn is so small), but because lots more cache misses caused the CPU to wait for data from memory. Did you profile the code for cache performance?
[/source]

I didn't profile it, but judging from the complexity of RBT insertion code (there's about 30 more conditional statements required per insertion, on average), and the fact that it uses nodes that could be spread all around the memory, I'd say you're probably right about the cache misses.

Plus, the RBT nodes required more memory per node than a heap node (I need to store color, and three references to the parent, left, and right children for RBT's, and nothing for Heaps.)

ToohrVyk

238

ToohrVyk

Feb 2, 2006 at 8:12 AM

I encountered this "pausing" situation not very long ago, where my events would be rescheduled. I operated these modifications the following way:

All my events are versioned. When an event is scheduled, its current version is stored along with it. When it is extracted from the priority queue, if its actual version is different from the stored version, the event is assumed to be outdated and is discarded without being run.

Rescheduling can then be done by modifying the event version and inserting it into the queue with a different priority, which ends up being of O(log n) complexity.

You can decide to take an aggressive approach towards outdated events by removing them from the heap when you encounter them during a traversal, to reduce the heap size, if you have a lot of reschedules occuring. This also resolves to amortized O(log n) time for each reschedule, but slightly increases the speed of other operations.

iMalc

182

iMalc

Feb 2, 2006 at 12:07 PM

How about keeping your existing heap, and adding a hash-table of key->position? Use the seperate chaining technique of course.

Then you can find the positions of your timed events in constant time. You just have to make sure to adjust the item position in the hash table, as it moves in the heap.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.