// simple-minded version - have heapRebuild, heapInsert etc as simple functions rather than
// member functions of class heap
// ros
#include <iostream>
#include <cstdlib>
const int MAX_HEAP = 20;
using namespace std;
void heapInsert(int a[],int size, const int& newItem);
void heapDelete(int a[],int size);
void heapRebuild(int a[], int root, int size);
int main()
{
   int n = 10;
   int a[] = {4,8,1,3,9,7,4,1,8,2};
   // make a heap
   for (int i = n/2; i >= 0; i--)
       heapRebuild(a,i,n);
   // repeatedly move biggest to sorted region and rebuild what's left of heap  
   int last = n-1;
   for (int i = 0; i < n;i++)
   {
      swap(a[0],a[last]);
      heapRebuild(a,0,last);
      last--;
   }
   // check if sorted
   for (int i = 0; i < n; i++)
     cout << a[i] << '\t';
   system ("pause");
}

void heapInsert(int items[],int size, const int& newItem)
// Method: Inserts the new item after the last item in the
// heap and trickles it up to its proper position. The
// heap is full when it contains MAX_HEAP items.
{
  if (size <= MAX_HEAP) {

    // place the new item at the end of the heap
    items[size] = newItem;
    
    // trickle new item up to its proper position
    int place = size;
    int parent = (place - 1)/2;
    while ( (parent >= 0) &&  (items[place] < items[parent] ))
    {  // swap items[place] and items[parent]
          swap(items[place], items[parent]);	         
          // move up to parent
          place = parent;
	      parent = (place - 1)/2;
    } // end while
    
    ++size;
  }
} // end heapInsert
 
void heapDelete(int items[],int size)
// Method: Swaps the last item in the heap with the root
// and trickles it down to its proper position.
{
   if (size >0 )
   {  
      items[0] = items[--size];
      heapRebuild(items,0,size);
   } // end if
} // end heapDelete

void heapRebuild(int items[], int root, int size)
{
   // if the root is not a leaf and the root's search key
   // is less than the larger of the search keys in the
   // root's children
   int child = 2 * root + 1; // index of root's left
                             // child, if any

   if ( child < size )
   {  // root is not a leaf, so it has a left child at child
      int rightChild = child + 1; // index of right child,
                                  // if any

      // if root has a right child, find smaller child
      if ( (rightChild < size) &&
           (items[rightChild] < items[child]) )
         child = rightChild; // index of smaller child

      // if the root's value is larger than the
      // value in the larger child, swap values
      if ( items[root] > items[child] )
      {   
         swap(items[root],items[child]);
         // transform the new subtree into a heap
         heapRebuild(items,child,size);
      } // end if
   } // end if

   // if root is a leaf, do nothing
}