Chapter 15

Advanced Data Types and Techniques


15.0 Chapter Goals
     15.1.1 B-trees Defined
15.2 Implementing and Testing a Semi-Generic B-tree
15.3 Heaps
     15.3.1 Heaps Defined
     15.3.2 Heaps as Binary Trees
     15.3.3 Defining the Heap
15.4 Implementing and Testing a Semi-Generic Heap
15.5 Array Implementation and Sorting With Heaps
     15.5.1 Heapsort
15.6 Toward More Generic Structures
     15.6.1 Low Level Assignment Routines
15.8 Pointers and Memory Management Revisited
     15.8.1 Orphans
     15.8.2 Garbage
     15.8.3 Fragmentation
     15.8.4 Defragmentation and Garbage Collection
     15.8.5 Handles
15.9 Pointers and Generic Structures
     15.10.1 Generic Sorts Defined
15.12 Assignments
Contents