Chapter 11
Tree 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.


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