// HeapSort - sorts vector of the length n

class   HeapNode
{
     double value; 
     HeapNode *left; 
     HeapNode *right; 
     HeapNode *father; 
     int id; 

   panic (char* string)
   { cout << string << endl; 
     exit (0); 
   }
   
   double  promote (void)
   {
       if (left && right) {                 
          if (left->value > right->value) {
              right->father  = left; 
              left->promote (); 
          }  

          else { 
              left->father = right ; 
              right->promote () ; 
          } 

       else if (left)   left->promote () ; 
       else if (right)  right->promote ();  

       if (!father)   // father == NULL => the node is on the top
       { 
           if (left)     

   } 


   private : 
     HeapNode (void)
     { value = 0; left = right = father = 0; id = 0; 
     }
     HeapNode (int idt; double val, HeapNode *parent)
     {  value = val; father = parent; 
        left = right = 0; id = idt;  
     } 
     HeapNode (int idt; double val, HeapNode *parent, 
               HeapNode *ls, HeapNode *rs)
     {  value = val ; father = parent; 
        left = ls, right = rs; id = idt;  
     } 
     ~HeapNode (0) { 
       if (father)  {
             if (father->left->id == id) father->left = 0; 
             else if (father->right->id == id) father->right = 0;
             else nodepanic ("Pointer arithmetics wrong in ~HeapNode()" );
       }   
       if (left)  left->father = 0; 
       if (right) right->father = 0; 
     } 

}; 



// sorts an array ra[1..n] into ascending numerical order using the
// Heapsort algorithm. ra is replaced by its sorted rearrangenment.

void   HeapSort (double ra[], unsigned long n)
{
      unsigned long i, ir, j, l; 
      double   rra; 

      if (n <  2) return; 

 // l is decremented down to 1 during heap creation pahase. Once
 // l = 1  ir will be decremented down to 1 during selection phase

      l = (n >> 1)+1;
      ir = n; 



}