Heap Sort

Heapsort is another sorting algorithm. Heapsort uses Max Binary Heap and works on Selection Sort to improve its time performance from O(N²) to O(N LogN), which is the best for comparison based sorting. Quicksort is still better but it shows the benefit of Binary Heap.

Two important steps for Heapsort are:
  - Heapify
  - BubbleDown

Heapification works on the entire array (as opposed to Adding each element individually) and is shown to be O(N). Adding each element individually using Add will be O(N LogN). BubbleDown is the same as used when root is extracted in a Max Binary Heap.

Using Max Binary Heap, Heapsort can be used to sort in ascending order. To do a descending order sort, Min Binary Heap can be used.

Heapify:

Heapsort Algorithm:

Tests for Heapsort:

Running Median

Goal: Compute median of data which is changing.
Median: The median is the value separating the higher half of a data from the lower half.
Steps involved in computing median would be to sort the data and then find the mid point. Best sorting Algorithm can give us O(N Log N), a linearithmic solution. This can be expensive for large datasets if data is added/removed frequently. 

Binary Heap is a very useful data structure for this purpose mainly because of its support in O(log N) for insert/deletion. It achieves this due to its logical representation of being a complete and balanced binary tree. 

Following is the code for doing so:


Test/Validation:

Max Binary Heap

Binary Heap represents a Priority Queue with an array as a backing store. Array stores data
logically represented as a complete and balanced Binary Tree.

A Max Binary Heap satisfies the property that Children are GREATER than parent.
Basic operations supported by Max Binary Heap are:

- Extract (or extracts the maximum value), an O(Log N) operation.
- Add, an O(Log N) operation.

Critical method for Adding a value to Binary Heap is to BubbleUp (if needed) as each addition
// is done at the end of array and it may need to Bubble Up till Max Binary Heap Property
// is satisfied.
// Extracting is accomplished as follows:
// - We need to remove the first element of the array an O(1) operation
// - We do this by swapping it with the last element of the array and then
// - Bubbling down the root(which was the last element) to ensure Max Binary Heap
// property is satisfied.
// - Bubbling down is accomplished by swapping the parent with the GREATER of its
// children(MaxHeap)
// Other Important aspects, for a ZERO based array (Wikipedia has good detail):
// Parent: (index - 1) / 2
// Left Child: 2*parentIndex + 1
// Right Child: 2*parentIndex + 2

Min Binary Heap

Binary Search

Generic Version

Two Sum

Algorithms for finding numbers in an array which adds up to a specified sum.

Shuffling

Following is an algorithm(Knuth Shuffle or Fisher-Yates Shuffle) to shuffle elements of an array in O(N).


Generic Version