Saturday, December 10, 2016

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

No comments:

Post a Comment