old stuff: algorithms

1 files changed, 300 insertions, 0 deletions

diff --git a/algorithms/heap.cc b/algorithms/heap.cc
new file mode 100644
index 0000000..82d05ac
--- /dev/null
+++ b/algorithms/heap.cc
@@ -0,0 +1,300 @@
+#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;
+}
+