Defining the storage heap
It isn’t easy to give a good definition of a heap (in the sense of a storage heap) but here is a shot at it.
A heap is a data structure consisting of a pair (H,B) of substructures, operations (split,join), and attribute A where:
H is a set of sequentially addressable elements. That is, the elements form a sequence, each element has an integer associated with it (its address) and the difference between the addresses of successive elements is a constant, w. Let h_i be the address of the initial element of H and h_f be the address of the final element of H.
B is a set of integers such that (1) each element b of B is an address of an element of H, and (2) h_i and h_f are elements of B. From this definition we can define the successor succ(b) of each element (h_f has no successor) and we can order B if we wish.
Given the construction of succ on B we can define block(b) as the set of elements in H such that their addresses a satisfy
b <= a < succ(a)It is trivial to prove that the blocks of B divide H into disjoint subsets that cover H.
The attribute A is defined for elements of B. A(b) may have either of two values – free and inuse. A block b is said to be free if A(b) = free and in use if A(b) = inuse.
An address, h, of H is said to be free if A(largest address b in B that is <= h) = free and in use otherwise.
Now for the two operations:
The above definition covers defining a storage heap. It establishes what blocks are, what the sequence of blocks is, and how to alter the sequence of blocks.
The important thing here is that free lists/allocated lists are not basic abstractions; rather they are derived concepts based on the primitive concept of a block and the operations performed on a set of blocks.
This page was last updated August 22, 2010.