The Heap

A storage pool in which regions of memory are dynamically allocated is often called a heap . For example, in C++ the space for a variable is allocated essentially in one of three possible places: Global variables are allocated in the space of initialized static variables ; the local variables of a procedure are allocated in the procedure's activation record , which is typically found in the processor stack ; and dynamically allocated variables are allocated in the heap. In this context the term heap is taken to mean the storage pool for dynamically allocated variables.

In Chapter  we consider heaps and heap-ordered trees in the context of priority queue implementations. Unfortunately, the only thing that the heaps of Chapter  and the heap considered here have in common is the name. While it may be possible to use a heap (in the sense of Definition ) to manage a dynamic storage pool, typical implementations do not. In this context the technical meaning of the term heap is closer to its dictionary definition--``a pile of many things.''[9]

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.