Talk:Treap

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] treap

I'm not sure the priority has to be random, even though a random priority can be used to help avoid worst-case insertions into a binary search tree. I believe that a treap resolves to a priority queue if non-random priorities are used.

[edit] Min heap versus max heap

In the original Aragon and Seidel paper, the illustrations showed a max heap ordering. Since the priority of a node is randomly generated, their is a small chance that a child and a parent could have the same priority. MegaHasher 00:20, 6 August 2007 (UTC)

[edit] Plagiarized material in the Article

A majority of the Definition section looked like it was plagiarized wholesale from a webpage (apparently from 2003) at Cornell, and no attribution was given. I removed the material and added an external link. 71.182.188.252 19:47, 4 December 2007 (UTC)

My change was reverted as vandalism. Here is the webpage that I think the material was taken from: http://www.cs.cornell.edu/Courses/cs312/2003sp/lectures/lec26.html. Kstauffer 19:54, 4 December 2007 (UTC)

I removed it again. We'll see whether it sticks this time. It would probably have helped to use a more detailed edit summary — a large removal of material by an anonymous user with no explanation looks at first glance a lot like vandalism, so it's easy to understand why it was reverted. —David Eppstein 20:55, 4 December 2007 (UTC)