Tree Project

**<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.

- equality : x==y <==> x,y are identical
- totality : only one of the following is true

x > y, x < y, x == y , for all x , y - consistency : x > y <==> y < x

x >= y <==> ((x>y)||(x==y)) (p.494)

x <= y <==> ((xx != y <==> !(x==y)

- 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.

- the entry of a node is >=

the entries of its children - the tree is a compelete binary tree.

eq.

**<3> The Piority Queue ADT with Heaps **

- priority gueue :

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

A entry with highest priority always leave first.

- heap impleentation of priority gueue
- the entry of a node has a prionty that is

greater than or equal to the priority of its children. - the tree is a comp;ete binary tree

**Note :**- a heap is a complete binary tree which is

more easily implemented with an array. - 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.

- the entry of a node has a prionty that is
- Basic operation on a heap
- adding an entry
- algorithm
- add the new entry to the first available

location in the heap. - while ( the new entry has a priority higher than its parent)
swap the new entry with its parent.

**Note :**- the upward swapping process is called

reheapification upward. - 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

- using the vector class will certainly a good

choice to implement a dynamic array.

- add the new entry to the first available
- removing an entry

- algorithm
- copy the last entry of the heap to the

root and delete the last entry.

- while ( the entry has a priority lower than one of its children)

swap with the higher-priority child; (p.500)

**Note :**- the downward swapping process is called

reheapification downward. - for a gueue, new entry is added to the

end and delete at the beginning which is the

root of heap.

- copy the last entry of the heap to the

- adding an entry