Data Structures and algorithms

A data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow the most efficient algorithm to be used.

Type of data structures:
1. Base data structures:
a. Primitive types -char, int, string, double, float.
b. Composite types -union, struct.
2. Linear data structures:
List - array, linked list, line(stack,queue, Deque)
Associative array - Hash table, self-balancing binary search tree.
3. Non Linear data structures:
Graph data structures - adjacency list, adjacency matrix
Tree data structures - B-tree, Binary tree(AVL tree , Red-black tree),Heap, .

Ref: http://en.wikipedia.org/wiki/List_of_data_structures

A Binary heap is a simple heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:

• The shape property: all levels of the tree, except possibly
  the last one (deepest) are fully filled, and, if the last level of the
  tree is not complete, the nodes of that level are filled from left to
  right.
• The heap property: each node is greater than or equal to
  each of its children according to some comparison predicate which is
  fixed for the entire data structure. That is to say that Every Node in
  the Tree satisfies a predecided Relation with its children.

Ref: http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

Tree traversal methods:

To traverse a non-empty binary tree in preorder, perform the following operations:

1. Visit the node.
2. Traverse the left subtree.
3. Traverse the right subtree.

(This is also called Depth-first traversal.)

To traverse a non-empty binary tree in inorder, perform the following operations:

1. Traverse the left subtree.
2. Visit the node.
3. Traverse the right subtree.

To traverse a non-empty binary tree in postorder, perform the following operations:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the node.

Finally, trees can also be traversed in level-order, where we visit every node on a level before going to a lower level. This is also called Breadth-first traversal.

[edit] Example

In this binary search tree, Preorder traversal sequence: F, B, A, D, C, E, G, I, H Inorder traversal sequence: A, B, C, D, E, F, G, H, I Note that the inorder traversal of this binary search tree yields an ordered list Postorder traversal sequence: A, C, E, D, B, H, I, G, F Level-order traversal sequence: F, B, G, A, D, I, C, E, H

Search algorithms:
1. Binary Search -A binary search finds the median, makes a comparison to determine
whether the desired value comes before or after it, and then searches
the remaining half in the same manner. Another explanation would be:
Search a sorted array by repeatedly dividing the search interval in
half. Begin with an interval covering the whole array. If the value of
the search key is less than the item in the middle of the interval,
narrow the interval to the lower half. Otherwise narrow it to the upper
half.

Its running time is O(logn).

Sorting algorithms:

Heapsort is one of the best general-purpose sorting algorithms, a comparison sort and part of the selection sort family.

Although somewhat slower in practice on most machines than a good
implementation of quicksort, it has the advantages of worst-case O(n
log n) runtime. The primary advantage of the heap sort is its
efficiency. The execution time efficiency of the heap sort is O(n log
n). The memory efficiency of the heap sort, unlike the other O(nlogn)
sorts, is constant, O(1), because the heap sort algorithm is not
recursive. Heapsort is an in-place algorithm and is not a stable sort.

Ref:
http://tide4javascript.com/?s=Quicksort