Short Notes on Data Structures .

Arrays, linked lists ,stacks qeues - Linear Datastructures
Trees - Hierarchical DataStructures

-----------------------------------------------------------------------------------------
WHY LINKED LISTS ???

Arrays can be used to store linear data of similar types, but arrays have following limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2) Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.

Advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion

Drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
-----------------------------------------------------------------------------------------
Why Trees???

1. One reason to use trees might be because you want to store information that naturally forms a hierarchy. For example, the file system on a computer
2. Trees (with some ordering e.g., BST) provide moderate access/search (quicker than Linked List and arrays).
3. Trees provide moderate insertion/deletion (quicker than Arrays and slower than Unordered Linked Lists).
4. Like Linked Lists and unlike Arrays, Trees don’t have an upper limit on number of nodes as nodes are linked using pointers

-----------------------------------------------------------------------------------------
Heaps ???

A Binary Heap is a Binary Tree with following properties.
1) It’s a complete tree (All levels are completely filled except possibly the last level). This property of Binary Heap makes them suitable to be stored in an array.
2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to Min Heap.

Applications of Heaps:

1) Heap Sort: Heap Sort uses Binary Heap to sort an array in O(nLogn) time.
2) Priority Queue: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time. Binomoial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also efficiently.
3) Graph Algorithms: The priority queues are especially used in Graph Algorithms like Dijkstra’s Shortest Path and Prim’s Minimum Spanning Tree.

------------------------------

Heapsort algorithm has limited uses because Quicksort is better in practice. Nevertheless, the Heap data structure itself is enormously used. Following are some uses other than Heapsort.
Priority Queues are implemented using Heap data structure

----------------------------------------

Why is Binary Heap Preferred over BST for Priority Queue?

A typical Priority Queue requires following operations to be efficient.

->Get Top Priority Element (Get minimum or maximum)
->Insert an element
->Remove top priority element
->Decrease Key.

A Binary Heap supports above operations with following time complexities:
->O(1)
->O(Logn)
->O(Logn)
->O(Logn)

A Self Balancing Binary Search Tree like AVL Tree, Red-Black Tree, etc can also support above operations with same time complexities

So why is Binary Heap Preferred for Priority Queue?

-->Since Binary Heap is implemented using arrays, there is always better locality of reference and operations are more cache friendly.
-->Although operations are of same time complexity, constants in Binary Search tree are higher. We can build a Binary Heap in O(n) time. Self Balancing BSTs require O(nLogn) time to construct.
-->Binary Heap doesn’t require extra space for pointers.
-->Binary Heap is easier to implement.

----------------------------

Is Binary Heap always better?
-->Although Binary Heap is for Priority Queue, BSTs have their own advantages and the list of advantages is in-fact bigger compared to binary heap.

Searching
BST : O(Log n) --better than heap
HEAP : O(n)

-->*Searching an element in self-balancing BST is O(Logn) which is O(n) in Binary Heap.
Similarly
-->*We can print all elements of BST in sorted order in O(n) time, but Binary Heap requires O(nLogn) time.
-----------------------------------------------------------------------------------------