<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
   1. adding an entry

      

      

   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. 
         

         

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