An interesting paper/article on this topic considers the behavior of caching/paging on the overall layout of the heap; The idea being that it’s vastly more costly to pay for a cache miss or page in than nearly any other part of a datastructure’s implementation. The paper discusses a heap layout that addresses this.
You’re Doing It Wrong
by Poul-Henning Kamp