DIR Return Create A Forum - Home
       ---------------------------------------------------------
       Class H22
  HTML https://classh22.createaforum.com
       ---------------------------------------------------------
       *****************************************************
   DIR Return to: exercises
       *****************************************************
       #Post#: 48--------------------------------------------------
       the Heap
   DIR By: SpiderGoat
       Date: March 25, 2014, 5:12 am
       ---------------------------------------------------------
       definition:
       nearly complete tree.
       heap is a like family. every node is "bigger then the followed.
       child < father. root is biggest.
       that is the structure of context-switch's priority. easier to
       navigate for highest to lowest.
       implementation:
       binary tree as array.
       take an array, and order it like:
       left first, then right.
       then left's children (2i+1), and the right's children (2i+2).
       every layer start in cell 2^i - 1
       whole tree 2^(i+1) - 1
       last father is size/2.
       last cell is null.
       do it with VECTOR.
       
       macros:
       parent(i)  
       left(i)  
       right(i)  
       
       take an array of unique (non-duplicated) items, and order it as
       heap.
       build max heap (could be min heap as well)
       functions:
       max-heapify - maintain it
       insert new in top (and send to max-heapify)
       find max
       print
       num of items
       build
       destroy
       build/maintain
       max heapify (A=value,i=index) pushes down a lower value A[i]
       every "pointer" is actually an index in the array.
       every index believes there are heaps bellow, but if not bigger
       should be push downwards.
       algo:
       if new father is bigger than one of children (in 2i+1 and
       2i+2),
       swap new father with max of children
       check again with next level until last father-level, which
       is size/2.
       
       build heap - do max heapify from bottom up from youngest
       parrent
       create from bottom upwards.
       go from last father.
       size - actual exists
       length - number of places to fill.
       for i = sizeA/2 to 1
       max-heapify(A,i)
       
       insert
       put in last children.
       max heapify it.
       *****************************************************
       Page 1 of 1