This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||
|
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
There are many inconsistencies in the Selection Algorithm example:
Anyway, the algorithm described in Chazelle's paper is slightly different.
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)
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)
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)
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||
|
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
There are many inconsistencies in the Selection Algorithm example:
Anyway, the algorithm described in Chazelle's paper is slightly different.
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)
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)
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)