Talk:Soft heap

heap

if there could be, there needs to be a link to corruption. because to me, it doesn't make sense just with the word "increasing". - -evesummernight July 16 2005

In this case all it really means is changing the value from a correct value to an incorrect value. I'll try and clarify this somehow. Deco 19:11, 17 July 2005 (UTC)

Inconsistencies

There are many inconsistencies in the Selection Algorithm example:

• The description says n/2 elements are deleted at each step, but both the listing and the T(n) expression consider n/4 deleted elements.
• The 25%/75% to 75%/25% split would be correct if the corruption was undefined, but since the corruption always changes the key to a larger value, the actual split would be 50%/50% to 75%/25%, if n/2 elements are removed. If n/4 elements are removed, the split would be 25%/75% to 50%/50%.
• The T(n) expression doesn't consider the time of the "partition" call.

Anyway, the algorithm described in Chazelle's paper is slightly different.

I believe that I have removed the contradictions and improved the explanation of this algorithm. Bender2k14 (talk) 15:56, 24 September 2009 (UTC)

This line in the algorithm: "if k = 1 then return minimum(a[1..n])" does not seem to match the text (we are searching for largest k, so shouldn't we return the maximum here?). I may have misunderstood Wppds (talk) 02:48, 1 April 2019 (UTC)

Link Suggestion

There is a new paper by Kaplan and Zwick introducing a new soft heap variant. It has the same properites as Chazelle's original data structure, but with a much(!!!) simpler implementation and analysis. I'd suggest to include it as a reference.

H. Kaplan, U. Zwick: A simpler implementation and analysis of Chazelle's soft heaps. In Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, 2009, 477-485 141.20.24.38 (talk) 20:22, 10 February 2009 (UTC)

Done. Bender2k14 (talk) 23:41, 22 September 2009 (UTC)

Insertion sort?

Shouldn't that be bubble sort? As far as I can tell, bubble sort on a near-sorted array should be fast (close to O(n)). Insertion sort doesn't benefit here at all, on contrary, running insertion sort with an already sorted array is the worst case situation (unless you are smart enough to work backwards). —Preceding unsigned comment added by 138.246.7.176 (talk) 14:57, 9 April 2010 (UTC)

You are wrong, Insertion sort on sorted array takes only O(n) time. You just do nothing at each index as you move forwards. — Preceding unsigned comment added by 152.78.229.6 (talk) 23:28, 27 May 2011 (UTC)

Better explanation of corruption

I obviously do not understand how soft heaps works, but I would like to know whether this question could be answered in English somehow: What exactly is the effect of corruption? Does it mean that the data structure is not actually guaranteed to return the minimum when you ask it to? If so, is it really a priority queue? It can't be that all operations are O(1) and at the same time all operations are correct. Then one could always sort in linear time. Something has to yield. — Preceding unsigned comment added by 188.126.203.251 (talk) 17:17, 23 August 2012 (UTC)

I rewrote some parts of the explanation, hopefully it clarifies some of the misunderstandings. Cheers. — Preceding unsigned comment added by 134.96.49.147 (talk) 20:41, 4 May 2013 (UTC)