Learn Algorithms by visualization

Representing a Binary (Min) Heap in an array. Heaps are usually always populated in BFS order so the leaf nodes are always at the last or penultimate level (as shown in the figure).

We see the same min-heap insertion procedure on a min-heap represented as an array in memory (instead of a tree with left & right child pointers).

Heaps are one of the more interesting and one of the relatively less emphasized data structures in undergraduate computer science. Using a min(or max)-heap, one can realize a sorting algorithm (heap-sort) that achieves the optimal sorting bound of O(n log n). In this visual, you can see how one can go about populating a min-heap (which we saw earlier). As you can see, each insertion costs O(log n) since you need to (in the worst case) move a newly inserted element up to the root of the...

How a Doubly Linked List works

Binary search over a sorted array to find an element. We always check the center element of the remaining part of the array to discard either the right or the left half from further consideration. Runtime complexity: O(lg n).

Selection Sort: Always select the smallest remaining element in the input element and copy it to the end of the output array. In some sense, this is an inverse of Insertion Sort, where you insert the next element from the input array into it's correct sorted order in the output array.

Advanced Data Structures (6.851). An awesome place to be!! http://courses.csail.mit.edu/6.851/ http://courses.csail.mit.edu/6.851/spring12/lectures/

Blue arrows indicate edges, and red arrows indicate the order of traversal. The numbers indicate when the traversal happened. Given the definitions of each of the tree traversals, try to reason why in-order traversal doesn't exist for general (non-binary) trees.

Insertion Sort proceeds by inserting every element in the input array in its correct (sorted) position in the output array.

Blue arrows indicate edges, and red arrows indicate the order of traversal. The numbers indicate when the traversal happened. Binary Tree Traversal is a specialized form of General Tree traversal, where the notion of in-order tree traversal is well defined.

How the array data structure works

Linear time array partitioning. This is a very important algorithm that is used as a subroutine in the Linear time Selection algorithm as well as in Quick Sort.

There are some common queries that are used almost everywhere, but they seem to be not executed very cleverly by most (all??) SQL execution ...

The Breadth First Search (BFS) ordered tree traversal. Blue arrows are the graph edges and red arrows indicate the order in which nodes are traversed in BFS order.

Randomized Selection in O(n) time. We use the O(n) time partitioning algorithm to partition the array around a randomly chosen pivot to approximately halve our search space at every step. The runtime complexity of our solution (randomized) is: O(n + n/2 + n/4 + n/8 + ... + 1) = O(2n) = O(n).