<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 <==> ((x
x != 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.
<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
- 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.
- Basic operation on a heap
- adding an entry
- 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.
- the upward swapping process is called
- 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.
- removing an entry
- 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)
- the downward swapping process is called
- for a gueue, new entry is added to the
end and delete at the beginning which is the
root of heap.