Talk:Soft heap

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
???	This article has not yet received a rating on the assessment scale.
???	This article has not yet received an importance rating on the assessment scale.

[edit] 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)

[edit] 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.