/ Max-heap class
template <class Elem, class Comp> class maxheap {
private:
  Elem* Heap;          // Pointer to the heap array
  int size;            // Maximum size of the heap
  int n;               // Number of elements now in the heap
  void siftdown(int);  // Put element in its correct place
  void siftup(int);
public:
  maxheap(Elem* h, int num, int max)     // Constructor
    { Heap = h;  n = num;  size = max;  buildHeap(); }
  int heapsize() const       // Return current heap size
    { return n; }
  bool isLeaf(int pos) const // TRUE if pos is a leaf
    { return (pos >= n/2) && (pos < n); }
  int leftchild(int pos) const
    { return 2*pos + 1; }    // Return leftchild position
  int rightchild(int pos) const
    { return 2*pos + 2; }    // Return rightchild position
  int parent(int pos) const  // Return parent position
    { return (pos-1)/2; }
  bool insert(const Elem&);  // Insert value into heap
  bool removemax(Elem&);     // Remove maximum value
  bool remove(int, Elem&);   // Remove from given position
  void buildHeap()           // Heapify contents of Heap
    { for (int i=n/2-1; i>=0; i--) siftdown(i); }
  void swap(Elem *, int, int);
  int find (const Elem& E)   //returns position of an element..to find a duplicate with 
	 {						 // the highest propability and return its position
	  int pos;
		  for (int i = 0 ; i < n; i++)
				 { 
					  if ( E.ID == Heap[i].ID )
					  {
						  pos = i ;
						 for (int j = i ; j < n; j++)
							{
							  if ( E.ID == Heap[j].ID )
							  {
									if(Heap[j].p > Heap[pos].p)
									{	
										pos = j ;
										break;
									}
							  }
							}
						break;
					  }
				 }
		  return pos;
	 }
  bool exist (const Elem& E)  // checks if element exists in the heap.. if it doesnt after delete, then it should also be deleted from the tree
  {
	  for (int i = 0 ; i < n; i++)
		 {
		  if( E.ID == Heap[i].ID  )
		  {  return true ; }

		}
	  return false ;
	}
  void print()
	  {
		   if (n == 0)
		   {
			   cout<<"HEAP IS EMPTY"<<endl;
			}
		   else
		   {
		   cout<<"Heap is arranged by order of priority \n\t  <ID,Priority> \n"<<endl;
			 for (int i = 0 ; i < n; i++)
				 { 
					 cout<<Heap[i];
				 }
			  cout<<endl; 
		   }

	  }
};

template <class Elem, class Comp> // Utility function
void maxheap<Elem, Comp>::siftup(int pos) {
while ((pos!=0) &&
         (Comp::gt(Heap[pos], Heap[parent(pos)]))) {
    swap(Heap, pos, parent(pos));
   	pos = parent(pos);
	}
}

template <class Elem, class Comp> // Utility function
void maxheap<Elem, Comp>::siftdown(int pos) {
  while (!isLeaf(pos)) {     // Stop if pos is a leaf
    int j = leftchild(pos);  int rc = rightchild(pos);
    if ((rc < n) && Comp::lt(Heap[j], Heap[rc]))
	{	
		j = rc;        // Set j to greater child's value
	}
    if (!Comp::lt(Heap[pos], Heap[j])) return; // Done
    swap(Heap, pos, j);
    pos = j;         // Move down
  }
}

template <class Elem, class Comp> // Insert element
bool maxheap<Elem, Comp>::insert(const Elem& val) {
  if (n >= size) return false; // Heap is full
  int curr = n++;
  Heap[curr] = val; // Start at end of heap
    siftup(curr) ;
  
return true;
}

template <class Elem, class Comp> // Remove max value
bool maxheap<Elem, Comp>::removemax(Elem& it) {
  if (n == 0) return false; // Heap is empty
  swap(Heap, 0, --n);       // Swap max with last value
  if (n != 0) siftdown(0);  // Siftdown new root val
  it = Heap[n];             // Return deleted value
  return true;
}

// Remove value at specified position
template <class Elem, class Comp>
bool maxheap<Elem, Comp>::remove(int pos, Elem& it) {
  if ((pos < 0) || (pos >= n)) return false; // Bad pos
  swap(Heap, pos, --n);           // Swap with last value
  while ((pos != 0) &&
         (Comp::gt(Heap[pos], Heap[parent(pos)])))
    swap(Heap, pos, parent(pos)); // Push up if large key
  siftdown(pos);      // Push down if small key
  it = Heap[n];
  return true;
}

template <class Elem, class Comp>
void maxheap<Elem, Comp>::swap(Elem * heap, int x, int y) {

	Elem temp = heap[x];
		 heap[x]=heap[y];
		 heap[y]=temp;	 

}

#include <iostream>
using namespace std;

void insertSpot(int option)
{

  
  int arrayValue;
  int ar[32];
  for(int i = 32; i > 0; i--)
  {
      arrayValue = option % 2;
      cout << "arrayValue = " << arrayValue << endl;
      //cout << "option = " << option << endl;
      option = option / 2;
      ar[i] = arrayValue;
      if(arrayValue == 0)
        cout << "move left\n";
      if(arrayValue == 1)
        cout << "move right \n";
      if(option == 0)
        break;
      //cout << i;
  }
}

int main()
{
  int option;
  cout << "Please enter a number: ";
  cin >> option;
  insertSpot(option);
  return 0;
}

#include <iostream>
using namespace std;

void insertSpot(int option)
{
  int arrayValue;
  bool isOne = false;
  int ar[32];
  for(int i = 32; i > 0; i--)
  {
      arrayValue = option % 2;
      cout << "arrayValue = " << arrayValue << endl;
      cout << "option = " << option << endl;
      option = option / 2;
      ar[i] = arrayValue;
      if(arrayValue == 1)
        isOne = true;
    if(isOne)
    {
      if(arrayValue == 0)
      {  
         cout << "move left\n";
         //cout << "Inside if arrayValue = 0 and option is " << option << endl;
      }
      if(arrayValue == 1)
      {
         cout << "move right \n";
         //cout << "inside if arrayVallue = 1 and option is " << option << endl;
      }
      if(option == 0)
      {
         break;
      }
    }
  }
}

int main()
{
  int option;
  cout << "Please enter a number: ";
  cin >> option;
  insertSpot(option);
  return 0;
}