Chapter 11Tree Project

11.1 Heap

<1> total order semantics (p.185)

a total order semantics for a class requires the
six comparsion operators ( == , != , >=, <= , > , < ) to
be defined, forming a total order that meets.

1. equality : x==y <==> x,y are identical
2. totality : only one of the following is true
x > y, x < y, x == y , for all x , y
3. consistency : x > y <==> y < x
x >= y <==> ((x>y)||(x==y)) (p.494)
x <= y <==> ((x x != y <==> !(x==y)
4. transitivity : for all x,y,z
( x < y ) and ( y < z ) ==> ( x < z )

<2> heap storage rules

a heap is a binary tree where the entries of
the nodes can be compared with a total order semantics,
In addition, extra two rules are followed.

1. the entry of a node is >=
the entries of its children
2. the tree is a compelete binary tree.

eq.

<3> The Piority Queue ADT with Heaps

1. priority gueue :
a gueue in which every entry has an associated number call priority.

A entry with highest priority always leave first.

2. heap impleentation of priority gueue

1. the entry of a node has a prionty that is
greater than or equal to the priority of its children.
2. the tree is a comp;ete binary tree

Note :

1. a heap is a complete binary tree which is
more easily implemented with an array.
2. if one knows the maximum size of a heap in advance,
then use a fixed-sized array. Otherwise, one may implement
the heap by a dynamic array which grows and shrinks as required.
3. Basic operation on a heap

2. algorithm
1. add the new entry to the first available
location in the heap.
2. while ( the new entry has a priority higher than its parent)

swap the new entry with its parent.

Note :

1. the upward swapping process is called
reheapification upward.
2. by using array to implement the heap, the
first available location of a heap is the
first available location of the array, which is
simply at the next location of the last item
3. using the vector class will certainly a good
choice to implement a dynamic array.
3. removing an entry

1. algorithm
1. copy the last entry of the heap to the
root and delete the last entry.
2. while ( the entry has a priority lower than one of its children)
swap with the higher-priority child; (p.500)

Note :

1. the downward swapping process is called
reheapification downward.
2. for a gueue, new entry is added to the
end and delete at the beginning which is the
root of heap.