Max/Min Heap - Algorithms and Problem SolvingAlgorithms and Problem Solving

Max/Min Heap - Algorithms and Problem SolvingAlgorithms and Problem Solving

Heap is a special data structure that has a shape of a complete binary tree (except possibly the deepest internal node) with a special property. We call it 'Heap Property'.

Heap property
All nodes are either greater than or equal to (for max heap) or less than or equal to (for min heap) each of its children.

Both the insert and extract (remove) operations modify the heap in O(log n) time to satisfy

1. The shape property Form a complete binary tree by adding or removing from the end of the heap.
2. The heap property Heap property is maintained by heapify the position of insert or delete i.e. traversing up or down the heap to maintain the order between parent and child.

Insert

1. Add the element to the end of the heap.
2. Maintain the heap property between parent and child recursively – lets call it heapify operation. If parent>=both children for max heap (i.e. parent<=both children for min heap) then stop.
3. If not, swap the max child for max heap (or min child for min heap) with its parent and recurse to the previous step (heapify).

Extract

1. Swap the root (element at 0) of the heap with the last element.
2. Remove the last element by shrinking the heap size by 1.
3. Maintain the heap property by doing heapify as described above; if they are in the correct order, stop.

Both are O(n) operation. Below, I have tried to implement a generic version max/min heap. In order to make a heap with primitive type make sure to use the corresponding object class as the type. For example, for int type data we need to use Integer as the generic type. This is because I restricted the generic type only to an object that is comparable (i.e. implemented comparable interface or explicitly provided a comparator). Integer, Long, Double, Character etc. classes implemented the Comparable interface (i.e. compareTo (other) method) for natural ordering of the corresponding primitive type data. To use the heap libraries with custom object either –

1. Either, implement the Comparable interface and provide compareTo(other) implementation for natural order (i.e. ascending order). That is,

            compareTo(other) = 0 if this == other           compareTo(other) = 1 if this > other           compareTo(other) = -1 if this < other

2. Or, provide to the constructor a customized Comparator interface implementation with the compare(o1, o2) method implemented for ascending order. That is,

            compare(o1, o2) = 0 if o1 == o2           compare(o1, o2) = 1 if o1 > o2           compare(o1, o2) = -1 if o1 < o2

Read full article from Max/Min Heap - Algorithms and Problem SolvingAlgorithms and Problem Solving