D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

§4.1 and deletion §4.2 sections a heap maintains heap order according
to the selected ordering strategy. These strategies are referred to as min-heap,

---

CHAPTER 4. HEAP
43
and max heap. The former strategy enforces that the value of a parent node is
less than that of each of its children, the latter enforces that the value of the
parent is greater than that of each of its children.
When you come across a heap and you are not told what strategy it enforces
you should assume that it uses the min-heap strategy. If the heap can be
configured otherwise, e.g. to use max-heap then this will often require you to
state this explicitly. The heap abides progressively to a strategy during the
invocation of the insertion, and deletion algorithms. The cost of such a policy is
that upon each insertion and deletion we invoke algorithms that have logarithmic
run time complexities. While the cost of maintaining the strategy might not
seem overly expensive it does still come at a price. We will also have to factor
in the cost of dynamic array expansion at some stage. This will occur if the
number of items within the heap outgrows the space allocated in the heap’s
backing array. It may be in your best interest to research a good initial starting
size for your heap array. This will assist in minimising the impact of dynamic
array resizing.

---

Chapter 5
Sets
A set contains a number of values, in no particular order. The values within
the set are distinct from one another.
Generally set implementations tend to check that a value is not in the set
before adding it, avoiding the issue of repeated values from ever occurring.
This section does not cover set theory in depth; rather it demonstrates briefly
the ways in which the values of sets can be defined, and common operations that
may be performed upon them.
The notation A = {4, 7, 9, 12, 0} defines a set A whose values are listed within
the curly braces.
Given the set A defined previously we can say that 4 is a member of A
denoted by 4 ∈ A, and that 99 is not a member of A denoted by 99 /
∈ A.
Often defining a set by manually stating its members is tiresome, and more
importantly the set may contain a large number of values. A more concise way
of defining a set and its members is by providing a series of properties that the
values of the set must satisfy. For example, from the definition A = {x|x >
0, x % 2 = 0} the set A contains only positive integers that are even. x is an
alias to the current value we are inspecting and to the right hand side of | are
the properties that x must satisfy to be in the set A. In this example, x must
be > 0, and the remainder of the arithmetic expression x/2 must be 0. You will
be able to note from the previous definition of the set A that the set can contain
an infinite number of values, and that the values of the set A will be all even
integers that are a member of the natural numbers set N, where N = {1, 2, 3, ...}.
Finally in this brief introduction to sets we will cover set intersection and
union, both of which are very common operations (amongst many others) per-
formed on sets. The union set can be defined as follows A ∪ B = {x | x ∈
A or x ∈ B}, and intersection A ∩ B = {x | x ∈ A and x ∈ B}. Figure 5.1
demonstrates set intersection and union graphically.
Given the set definitions A = {1, 2, 3}, and B = {6, 2, 9} the union of the two
sets is A ∪ B = {1, 2, 3, 6, 9}, and the intersection of the two sets is A ∩ B = {2}.
Both set union and intersection are sometimes provided within the frame-
work associated with mainstream languages. This is the case in .NET 3.5
1
where such algorithms exist as extension methods defined in the type Sys-