Boost logo

Boost :

Subject: [boost] GSoC 2011
From: mahbubul hasan (shanto86_at_[hidden])
Date: 2011-03-29 00:31:21


Hi,

I am Mahbub. I am a CSE graduate. I just saw you had a proposal regarding
queue and heap in GSoC 2010. In my undergraduate I did thesis on heaps. In
that time I learned soft heap, it might be interesting to you.

Here is the short description of soft
heap<http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3258&rep=rep1&type=pdf>.(
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3258&rep=rep1&type=pdf)

Soft heap is a heap like data structure but with some uncertainty. This data
structure supports insert, delete, merge, findmin. It does every work in
amortized constant time except insert operation which takes O( log 1/e )
where 0<e=<.5. Here e is error rate. The data structure will never contain
more than en corrupted elements.

There are two versions of soft heap. 1. By Binomial Tree 2. By forest of
binary tree

There is one more thing that might interesting to you. That is, in my
undergraduate I improved the running time of heap sort by significant amount
by applying pairing technique. The paper is submitted to International
Journal of Computer Mathematics and it is under review now. It mainly
improves Carlsson's variant of heapsort. It also improves the deletion
method proposed by Gonnet and Munro (Heaps on Heaps). [The heap is inplace,
that means no additional space is required]

It also improves the Weak Heapsort. WeakHeapsort is a sorting method which
requires O(n) additional bit to sort. However applying the pairing technique
it can be reduced to O(n/2) additional bit. It is known that weakheap is the
theoretically best known algorithm. [Best considering number of comparisons]

So I am just curious if you are interested in these types of algorithms. I
saw no possible proposal category where these fits in, but I thought you
might be interested.

Please let me know what do you think about this.

Mahbub


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk