2

From the paper that I was reading By Bernard chazelle https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/The%20Soft%20Heap.pdf

I failed to find Soft heap being used much in practical scenario. So, It would be helpful if someone could let me know why is it really useful.

Somit
  • 51
  • 3
  • 1
    In practice it isn't useful. It's hard to use data structures that give unpredictable wrong answers, and given the very marginal improvement, I don't think anyone would bother trying. – David Eisenstat Jan 03 '21 at 19:18

1 Answers1

0

I haven't red the article, only the abstract and I quote

The soft heap can be used to compute exact or approximate medians and percentiles optimally. It is also useful for approximate sorting and for computing minimum spanning trees of general graphs.

So it has some uses in the graphs' algorithms or in medians' computing.

In graph algorithms there's a popular algorithm called "Prim's Algorithmm" and it finds the minimum spanning trees of general graphs. I'm not 100% sure but I think Soft Heap are used in this algorithm.

You might be familiar with plain old heap, it is potent for its fast computing response time. Seems like Soft Heap share the same property.

Pierre-Olivier L'Espérance
  • 11
  • 2