Talk:Cartesian tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science  
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

Ca 1982 (unpublished article), C J Stephenson of IBM's T J Watson Research Center proposed the use of a Cartesian tree for the maintenance of a storage heap, referring to the concept as "Fast Fits". Basically, the nodes of the tree represent contiguous pieces of free space in the heap, with the address of the piece serving as the node's binary tree "key", and the size of the piece serving as the node's "priority".

Stephenson demonstrated that algorithms for adding a piece of free heap to the tree, coalescing adjacent pieces, and finding an available "best fit" piece could all be efficiently implemented.drh (talk) 02:06, 12 October 2011 (UTC)

Pseudocode[edit]

Pseudocode might be nice to have in the sections discussing the algorithm's implementation. — Preceding unsigned comment added by 2620:0:2820:2217:3EA9:F4FF:FE56:8B04 (talk) 17:45, 30 September 2013 (UTC)