Talk:Cheney's algorithm: Difference between revisions

Revision as of 15:59, 6 June 2007

Revision as of 05:44, 8 May 2008

Line 6:

==Recursion==

{{Expand|date=June 2007}}

:Is this algorithm recursive? Will it copy objects refererredreferred to by something referred to by something referenced from the stack? If so, it is not described that way. -- [[User:Beland|Beland]] 17:19, 24 May 2007 (UTC)

:: It is recursive - objects copied are handled after the objects on the stack by simply going through the new heap. This results in a breadth-first approach to reaching all the items, as both the stack and the heap itself act as queues of items to reach, and one is always adding to the end of the heap then scanning forward in either the stack or the heap.

Cheney's algorithm seems to produce among the ''worst possible'' structures if locality-of-reference is desired - objects referenced by other objects are neatly splattered across the entire heap due to the breadth-first-search implicit to the algorithm. And, yet, the lack of any requirement for a stack (which is necessary for a depth-first search) is part of what keeps Cheney's algorithm itself quite simple.