1.8 Heap

• Max(min) tree is each node is greater or equal to its children node.
• Heap is 1)complete 2) binary 3)Max(min) tree.
• Because Heap is complete binary tree. We can use an array to store it.
• insert is easier than you think, When you insert, put it on the end position, then exchange with parent.
  insert(x){ 
    int c = ++currentSize; 
    while(c!=1 && x>heap[c/2]){ //get its parent node and compare 
    heap[c] = heap[c/2];  //move down parent 
    ____________________________________________________________// move parent  down because it smaller 
    c/=2;  //move up a level 
    } 
    heap[c] = x;  //the right position of insert. 
    //at this time heap[c] has been moved away by previous 
    //statement heap[c] = heap[c/2] 
  } 
  ____________________________________________________________ //c is used to control level,  c/=2 move up level 
  ____________________________________________________________ //heap[c/2] get its parent
• Heap just support delete Max(Min) value. When delete, delete the first element, then put the end position element to the first position, then exchange it with either left child or right child.
  T y = heap[CurrentSize--]; 
  int i = 1, ci = 2; 
  //because ci will increase to get bigger one from two children. 
  //so I have to use another i to keep current level 
  while(ci<=CurrentSize){ 
    if(heap[ci]<heap[ci+1]) ci++; // get the bigger child 
   
    if(y>=heap[ci]{ 
     heap[i] = y;   // i always empty for a new value. 
     break; 
    } 
    ______________________________ //i is current node 
        ______________________________ //ci  is i biggest child node 
    heap[i] = heap[ci]; //move up child, insert is "move down parent" 
    i = ci;  //move to next level 
    ci *=2; 
  }
• Initialize a Heap: For an array, from the middle point, loop backward until reach head. the time complexity is O(n).
  for(int i = CurrentSize/2; i>=1;i--){ //from middle, backward 
   root = head[i] // get root node 
   child1 = root*2, child2 = root*2+1 // get two children 
   move bigger child to root. 
  }
• Heap just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels, whereas BST guarantees order (from "left" to "right"). If you want sorted elements, go with BST.
• In STL, heap is called priority_queue
  __________________________________________defaultcomparefunctionisless<T> 
   std::priority_queue<int, std::vector<int>, std::greater<int> > q2; 
      for(int n : {1,8,5,6,3,4,0,9,7,2}) 
          q2.push(n); 
      // 0, 1, 2 ,3 ,4, 5...