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 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)