#include <iostream>

using namespace std;


struct Node {
  int value;
  Node* pNext;
  Node* pLeft;
  Node* pRight;
};

struct Tree {
  Node* pRoot;
};


Node*
new_node(int value)
{
  Node* node   = new Node;
  node->value  = value;
  node->pNext  = NULL;
  node->pLeft  = NULL;
  node->pRight = NULL;
  return node;
}

void
delete_node(Node* pNode)
{
  if(pNode->pNext)
    delete pNode->pNext;
  if(pNode->pLeft)
    delete pNode->pLeft;
  if(pNode->pRight)
    delete pNode->pRight;
  delete pNode;
}

void
insert(Tree& tree, int value)
{
  int last = 0;
  int heap_pos_check = 0;
  int copy_pos;
  int father_index = 0;

  Node* father = NULL;
  Node* child = NULL;
  Node* p = NULL;

  if (tree.pRoot == NULL) {
    tree.pRoot = new_node(value);
    p = tree.pRoot;
  } else {
    p = tree.pRoot;

    for (last = 1; p->pNext != NULL ; last++)  {
      p = p->pNext;
    }

    p->pNext = new_node(value);
    child  = p->pNext;
    heap_pos_check = last + 1;

    while (heap_pos_check > 1) {
      copy_pos = heap_pos_check;
      father = tree.pRoot;

      for (father_index = 1; father_index < (copy_pos / 2); father_index++) {
        father = father->pNext;
      }

      if ((copy_pos % 2) == 1) {
        father->pRight = child;
      } else {
        father->pLeft = child;
      }

      if (father->value >= child->value) {
        break;
      } else {
        int temp;
        temp = child->value;
        child->value = father->value;
        father->value = temp;
        child = father;
        heap_pos_check = father_index;
      }
    }
  }
}

int
remove(Tree& tree)
{
  int tmp;
  int root_value;
  Node* p = NULL;

  if (tree.pRoot != NULL) {
    root_value = tree.pRoot->value;
  }

  else return -1;

  p = tree.pRoot;
  int temp;

  while(true) {
    if (p->pNext->pNext) {
      p = p->pNext;
    } else {
      break;
    }
  }

  tree.pRoot->value = p->pNext->value;
  delete_node(p->pNext);
  p->pNext = NULL;
  p = tree.pRoot;
  Node* hp = p;

  while((hp->pLeft != NULL) || (hp->pRight != NULL)) {
    if (hp->pLeft != NULL) {
      if (hp->pRight != NULL) {
        if (hp->pLeft->value < hp->pRight->value) {
          tmp = hp->pRight->value;
          hp->pRight->value = hp->value;
          hp->value = tmp;
          hp = hp->pRight;
        } else {
          tmp = hp->pLeft->value;
          hp->pLeft->value = hp->value;
          hp->value = tmp;
          hp = hp->pLeft;
        }
      } else {
        if(hp->pLeft->value > hp->value) {
          tmp = hp->pLeft->value;
          hp->pLeft->value = hp->value;
          hp->value = tmp;
          hp = hp->pLeft;
        } else {
          hp = hp->pLeft;
        }
      }
    }
  }
  return root_value;

}

void
sort_array(Tree& tree, int sorted[])
{
  int num_nodes = 0;
  Node* p = tree.pRoot;

  for(num_nodes = 0; p->pNext != NULL; num_nodes++) {
    p = p->pNext;
  }

  for (int i = num_nodes; i >= 0; i--) {
    sorted[i] = remove(tree);
  }
}

void
heap_array(int * a, int i, int n) {
  int j, tmp;
  while (2*i <= n) {
    j = 2*i;
    if (j<n)
      if (a[j] < a[j+1]) j++;
    if (a[i] < a[j]) {
      tmp=a[i]; a[i]=a[j]; a[j]=tmp;
      i=j;
    } else {
      i=n;
      i++;
    }
  }
}

void
heap_sort(int * a, int n) {
  int tmp;
  for (int i=n/2; i>=0; i--) heap_array(a, i, n);
  for (int i=n; i>=1;  i--) {
    tmp=a[i]; a[i]=a[0]; a[0]=tmp;
    heap_array(a, 0, i-1);
  }
}

void
prefix(Node* n)
{
  cout << n->value << endl;

  if(n->pRight) {
    prefix(n->pRight);
  }

  if(n->pLeft) {
    prefix(n->pLeft);
  }
}

void
infix(Node* n)
{
  if(n->pRight) {
    infix(n->pRight);
  }

  cout << n->value << endl;

  if(n->pLeft) {
    infix(n->pLeft);
  }
}

void
postfix(Node* n)
{
  if(n->pRight) {
    postfix(n->pRight);
  }

  if(n->pLeft) {
    postfix(n->pLeft);
  }

  cout << n->value << endl;
}

void
print_tree(Tree& t, int type)
{
  switch(type) {
    case 0:
      cout << "prefix" << endl;
      prefix(t.pRoot);
      break;
    case 1:
      cout << "infix" << endl;
      infix(t.pRoot);
      break;
    case 2:
      cout << "postfix" << endl;
      postfix(t.pRoot);
      break;
    default:
      cout << "?" << endl;
  }
}

int
main(void) {
  Node* root = new_node(0);
  Tree t;
  t.pRoot = root;

  insert(t, 2);
  insert(t, 4);
  insert(t, 5);
  insert(t, 6);
  insert(t, 3);
  insert(t, 1);

  cout << "tree with 7 nodes..." << endl;
  print_tree(t, 0);
  print_tree(t, 1);
  print_tree(t, 2);

  cout << endl << "-----" << endl;

  cout << endl << "heap_sort" << endl;

  int a[10] = {1,6,3,2,9,111,5,9,8,10};

  cout << endl << "before:" << endl;

  for(unsigned int i = 0; i<10; i += 1) {
    std::cout << a[i] << std::endl;
  }

  heap_sort(a, 10);

  cout << endl << "after:" << endl;

  for(unsigned int i = 0; i<10; i += 1) {
    std::cout << a[i] << std::endl;
  }

  return 0;
}