node *buildHeap(struct stack *s, int(*lt)(int, int))
{
    node *g = top(s);
    treeNode *b = g->treeN->parent;
    while(g->treeN->parent != NULL)
    {
        b = g->treeN->parent;
        if(b->right != NULL) //it's a right child
        {
            siftDown(b, lt);
            if(g->next->next != NULL)
            {
                g = g->next->next;
            }
        }
        else    //it's a left child
        {
            siftDown(b, lt);
            if(g->next != NULL)
            {
                g = g->next;
            }
        }
    }
    return g;
}

void hsort64(U128T records[], size_t count)
{
	int64_t start, end;
	U128T temp;

	status = 0;
	puts("Heapifying records");
	for (start=count/2-1; start>=0; start--) {
		if (bailout)
			exit(1);
		siftDown(records, start, count);
		status = count - 2*start;
	}

	status = 0;
	puts("Sorting records");
	for (end=count-1; end>0; end--) {
		if (bailout)
			exit(1);
		temp = records[end];
		records[end] = records[0];
		records[0] = temp;
		siftDown(records, 0, end);
		status = count - end + 1;
	}
}

void heapSort(int *a, int count) {
        int start, end;
        for (start = (count-2)/2; start >=0; start--) {
                siftDown( a, start, count);
        }//for

        for (end=count-1; end > 0; end--) {
                SWAP(a[end],a[0]);
                siftDown(a, 0, end);
        }//for
}//heapSort

void heapSort(void* buf, size_t size, size_t total, int (*compare)(void const* a, void const* b)) {
	int start, end;

	for(start = (total - 2) / 2; start >= 0; start--) {
		siftDown(buf, size, start, total, compare);
	}

	for(end = total - 1; end > 0; end--) {
		exch(buf, end, 0, size);
		siftDown(buf, size, 0, end, compare);
	}
}

void heapSortHelper (int* a, int first, int last)
{
    for (int i = last / 2; i >= first; i--)
    {
        siftDown(a, i, last);
    }
    for (int i = last; i > first; i--)
    {
        Sort::swap (a[i], a[first]);
        siftDown (a, first, i - 1);
    }
}

void heap_sort(int a[], int n){
	int i, temp;

	for (i = (n / 2)-1; i >= 0; i--)
		siftDown(a, i, n);

	for (i = n-1; i >= 1; i--){
		temp = a[0];
		a[0] = a[i];
		a[i] = temp;
		siftDown(a, 0, i-1);
	}
}

void internal_heapsort(int *a, int count)
{
  int start, end;

  /* heapify */
  for (start = (count - 2) / 2; start >= 0; start--) {
    siftDown(a, start, count);
  }

  for (end = count - 1; end > 0; end--) {
    SWAP(a[end], a[0]);
    siftDown(a, 0, end);
  }
}

void heapSort(LONG_T* keys, LONG_T* auxKey1, WEIGHT_T* auxKey2, LONG_T n)
{
	LONG_T i;

	for (i = (n/2)-1; i >= 0; i--)
		siftDown(keys, auxKey1, auxKey2, i, n);

	for (i = n-1; i >= 1; i--) {
		swapL(&keys[0], &keys[i]);
                swapL(&auxKey1[0], &auxKey1[i]);
                swapW(&auxKey2[0], &auxKey2[i]);
		siftDown(keys, auxKey1, auxKey2, 0, i-1);
	}

}

void HeapSortAsc( int *I ) /* sort array I in ascending order using heap sort algorithm */ 
{
	int i, tmp;
	//Make a heap!
	//Heapify
	for (i = (size-2)/2; i >=0; i--)
		siftDown(I,i,size);
	for (i = size-1; i >= 1; i--){
		tmp = I[0];
		I[0] = I[i];
		I[i] = tmp;
		siftDown(I,0,i);
	}
	return;
}

void heapsort(long * numbers, long n, int isort)
{
  long i, temp;
 
  for (i = (n / 2); i >= 0; i--)
    siftDown(numbers, i, n - 1,isort);
 
  for (i = n-1; i >= 1; i--)
  {
    temp = numbers[0];
    numbers[0] = numbers[i];
    numbers[i] = temp;
    siftDown(numbers, 0, i-1,isort);
  }
}

void heapify(RandomAccessIterator first, RandomAccessIterator last) {
    RandomAccessIterator start = first + (last - first)/2 - 1;
    while (start >= first) {
        siftDown(first, start, last-1);
        --start;
    }
}

void siftDown(int numbers[], int root, int bottom) 
{
	int maxChild = root * 2 + 1;	
	
	// Find the biggest child
	if(maxChild < bottom) 
	{
		int otherChild = maxChild + 1;
		// Reversed for stability
		maxChild = (numbers[otherChild] > numbers[maxChild])?otherChild:maxChild;
	} 
	else 
	{
		// Don't overflow
		if(maxChild > bottom) 
			return;
	}	
	
	// If we have the correct ordering, we are done.
	if(numbers[root] >= numbers[maxChild])
		return;	
	
	// Swap
	int temp = numbers[root];
	numbers[root] = numbers[maxChild];
	numbers[maxChild] = temp;	
	
	// Tail queue recursion. Will be compiled as a loop with correct compiler switches.
	siftDown(numbers, maxChild, bottom);
}

void heapify( TreeNode ** node){
	TreeNode * p = *node;
	while( p != NULL){
		siftDown( &p);
		p=p->getPrev();
	}
}

void heapSort( TreeNode ** rt, TreeNode ** lt, std::vector<int> & vec){
	TreeNode * temp = *lt;
	TreeNode * tempParent;
	//TreeNode * temp2;

	while( temp != NULL){
		if( temp == *rt){
			vec.push_back( (*rt)->getValue() );
			break;
		}
		vec.push_back( (*rt)->getValue() );
		(*rt)->setValue( temp->getValue() );
		tempParent = temp->getParent();
		if( tempParent->getRight() == temp){
			tempParent->setRight(NULL);
		}
		if( tempParent->getLeft() == temp){
			tempParent->setLeft(NULL);
		}
		temp = temp->getPrev();
		if( temp!=NULL){
			temp->setNext( NULL);
		}
		
		//delete temp1;
		//temp1 = NULL;
		siftDown( rt);
	}
}

    void siftDown(T (&a)[N], int index) {//max-heap
      while (2*index + 1 < N) {
        int l = 2*index + 1;
        if (l + 1 < N && a[l+1] < a[l]) {
          ++l;
        }
        if (a[l] < a[index]) {
          std::swap(a[l], a[index]);
        }
        index = l;
      }
#if INTRO_ALGRO
      int l = 2*index; //index start from 1
      int r = 2*index + 1;
      int largest = -1;
      if (l <= N && a[l] > a[index]) {
        largest = l; 
      }
      else {
        largest = index;
      }
      if (r <= N && a[r] > a[largest]) {
        largest = r;
      }
      if (largest != index) {
        std::swap(a[largest], a[index]);
        siftDown(a, largest);
    }
#endif
  }

void siftDown(treeNode *front, int(*lt)(int, int))
{
    treeNode *left = front->left;
    treeNode *right = front->right;
    treeNode *smallestOrLargest = front;
    int indicator = 0;  //swap indicator
    if(front->left != NULL && lt(left->value, smallestOrLargest->value))    //if there's a left child and it's value compares with the other
    {
        smallestOrLargest = left;
        indicator = 1;
    }
    if(front->right != NULL && lt(right->value, smallestOrLargest->value))  //if there's a right child and it's value compares with the other
    {
        smallestOrLargest = right;
        indicator = 2;
    }
    if(indicator == 0)  //no swap was made
    {
        return;
    }
    if(smallestOrLargest->value != front->value)    //if the original smallest or largest moved to a new node, swap and recursively call siftDown
    {
        swap(&smallestOrLargest->value, &front->value); 
        siftDown(smallestOrLargest, lt);
    }
}

void buildHeap(int *a, int n)
{
    for(int i=(n-2)/2; i>=0; i--)
    {
        siftDown(a, n, i);
    }
}

void heapsort(int arr[], int array_size)
{
  int i, temp;
  for (i = (array_size / 2); i >= 0; i--)
    siftDown(arr, i, array_size - 1);			//Heapify

  for (i = array_size-1; i >= 1; i--)
  {
    // Swap
    temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;

    siftDown(arr, 0, i-1);
  }
}

void HeapOrderedTree :: deleteMin(){
  if( !empty() ){
    swap( heap[1], heap[tail_index] );
    tail_index--;
    siftDown();
  }
}

 void drainHeap() {
     size_t const count = a.size(buf);
     for (ssize_t next = count; next > 1; next--) {
         a.swap(buf, next, 1);
         siftDown(1, next - 1);
     }
 }