[boost] GSoC 2010: Heaps and Queues

Subject: [boost] GSoC 2010: Heaps and Queues
From: Dan Larkin (danielhlarkin_at_[hidden])
Date: 2010-03-24 17:43:20

I'm another potential student throwing my hat in the ring for the heap 
project.  I'll save most of my personal details for my proposal, but for 
right now I thought I'd try to get a bit of a dialogue going with the 
community to help me understand what it is you guys are looking for and 
what it is I can work towards.  So I'll start with my current 
understanding of the situation.

The way I see it, the current heap implementations in boost/pending are 
rather fractured.  They just have simple push/pop interfaces with no 
mutability (well, there's mutable_heap.hpp, but that's separate and not 
fleshed out).  All in all, what seems to be needed is a standardized 
heap concept/API along with a few fully-implemented models.  Standard 
heap functionality begs the following functions:
  - findMin
  - deleteMin
  - insert
  - changeKey
  - merge
These can all be implemented quite efficiently (either worst case or 
amortized O(logn) time or better) for any heap model.  I would be 
looking to implement the d-ary, binomial, and Fibonacci heaps for sure, 
with relaxed and Brodal heaps as a possibility, should time allow it. 
These heap models would be built as extensions of a base Heap class, 
which could be easily wrapped in a PriorityQueue class which takes the 
heap-type as a construction parameter (and defaults to a d-ary heap for 
instance).

I know that a stable priority queue was mentioned in earlier discussion, 
but I'm not sure what to do about that just yet.  It'll take a little 
more thinking before I could say whether I think it'd fall under the 
scope of the summer project, or if it should be put on the back-burner 
for later addition to the library.

I guess that's basically how I see the problem so far.  Please let me 
know what you think, or what other sort of information/planning/etc. you 
would like to hear from me prior to my proposal/draft.

Dan Larkin