Notes on Data Structures

Excellent memory refreshers on the basics of data structures:
http://algosaur.us/data-structures-basics/#n00b (With very cute illustrations!)
http://www.geeksforgeeks.org/data-structures/

Memory refresher on time complexity:

Such complex, very wow – A guide to Algorithmic Complexity

Queue

Stack

Heap
– max-heap – all children are smaller than parent
– min-heap – all children are greater than parent
– Time complexity for insertion is O(logN)
– Heapsort => O(NlogN)

Binary Tree
– always of height logN

Sorting
insertion sort => O(N2)
– Good when array size is small or almost sorted
– bubble sort
– Mergesort => O(NlogN)
– Quicksort => O(NlogN)
– Key concept: Picks an element as pivot and partitions the given array around the picked pivot
– Best case O(NlogN), average case O(NlogN), worst case O(N2)

Hash table
O(1)

Count inversions

Leave a Reply