Efficiently manage handle for an array binary heap in C++?

Question

Is there a way to efficiently keep track of handles in an array binary heap?

Since there's no fast lookups built into traditional binary heaps, users need a 'handle_type' for delete or decrease_key on an arbitrary element in the heap.

You can't use a pointer or an index into the array, because heap operations will move the element's location around. I can't think of a simple solution using only stack-like structures the way a traditional heap implementation does. Otherwise, I'd have to use 'new/delete' and that feels inefficient.

I don't want to get too obsessed about pre-mature optimization, but I want this to be a part of my standard library of utilities, and so I'd like to put in a little effort to get to know what is considered best practice for this sort of thing.

Maybe just a naive implementation using 'new/delete' is the way to go here. But I'd like to get some advice from people smarter than me first, if that's ok.

The priority queue implementation in the C++ standard library seems to side-step this issue entirely by simply not supporting a 'decrease_key' operation. I've been leafing through CLRS, and they mention this issue but don't really discuss it:

we shall not pursue them here, other than noting that... these handles do need to be correctly maintained.

Is there a simple approach here I'm overlooking? What do "serious" libraries do when they need a general purpose array heap that needs a 'decrease_key' operation?

The easy way to do this is to delete the item, change its key, and re-insert it. If there is an in-situ algorithm, I've never seen one. It does seem that you will need some kind of a handle. — user207421
– user207421, Commented Sep 8, 2016 at 5:01
What do you mean with an "array binary tree"? An array binary tree is normally used on full binary trees (completely populated up to level n), so you don't waste space with the pointers. What is the purpose of what you want to implement? Please edit the question and explain your objectives, so we can give some hints about it. — Luis Colorado
– Luis Colorado, Commented Sep 8, 2016 at 9:19
@LuisColorado Sorry, I misworded. I meant to say 'array binary heaps'. Common heap implementations (e.g. in standard libraries of C++/Python) use arrays to represent the tree structure of heaps. — math4tots
– math4tots, Commented Sep 8, 2016 at 16:55
Ok, thanks. I know something about heap implementations, and also to array binary trees, but never head of an application that mixes both. — Luis Colorado
– Luis Colorado, Commented Sep 9, 2016 at 13:01

Ami Tavory · Accepted Answer · 2016-09-08 05:22:46Z

Is there a way to efficiently keep track of handles in an array binary tree?

It's hypothetically possible (but not very pretty). Internally, instead of storing an array of elements, the data structure would store an array of pointers (or smart pointers) to a struct containing an pair of an index and and element.

When an element is first inserted into position i in the array, the data structure would initialize the index of this struct to i.
As the data structure moves elements around the array, it should modify the index to reflect the new position.

The result of push can be a pointer to this struct (possibly wrapped in an opaque class). In order to access a specific element (e.g., for decrease_key), you would call some method of the heap with this return value. The heap would then

Know the address of the array (it is its member, after all)
Know the index within the array, through the struct you just sent it.

It could thereby implement decrease_key, for example.

However, there are probably better (and less cumbersome) solutions. Note that the above solution wouldn't alter the asymptotic complexity of the array heap, but the constants would be worse. Conversely, if you look at this summary of heap running times, you can see that a binary heap doesn't really have good performance for decrease_key operations. If you need that, you're probably better off with a Fibonnacci heap (or some other data structure). This leads to your final question

What do "serious" libraries do when they need a general purpose array heap that needs a 'decrease_key' operation?

Libraries such as boost::heap usually indeed implement other data structures more suited for more advanced operations (e.g., decrease_key). These data structures are naturally node based, and naturally support return values which are not invalidated so easily as in the array.

Collectives™ on Stack Overflow

Efficiently manage handle for an array binary heap in C++?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related