It provides constant time retrieval and logarithmic time removal of both the minimum and maximum elements in it.
This makes the min-max heap a very useful data structure to implement double-ended priority queue. Like binary min-heaps and max-heaps, min-max heaps support O(logn) insertion and deletion, can be built in time O (n) and are often represented implicitly in an array.
public class MaxHeap {
private int size;
private int[] maxHeap;
private static final int START_IDX = 1;
public MaxHeap(int mSize) {
this.maxHeap = new int[mSize+1];
}
/**
* 1. Insert the element at the last position.
* 2. Check whether the parent is smaller.
* 3. Swap Child and Parent.
* 4. Keep iterate the same till the Max-Heap property doesn't match.
* @param element
*/
private void insert(int element) {
maxHeap[++size] = element;
int currIdx = size;
while(currIdx>1 && maxHeap[currIdx]>maxHeap[parent(currIdx)]) {
swapElement(currIdx,parent(currIdx));
currIdx = parent(currIdx);
}
}
/**
* Swap two elements.
* @param currIdx
* @param parent
*/
private void swapElement(int currIdx, int parent) {
int temp = maxHeap[currIdx];
maxHeap[currIdx] = maxHeap[parent];
maxHeap[parent] = temp;
}
/**
* 1. Store the top element.
* 2. Replace it with last element and reduce the heap size by 1.
* 3. Heapify to restore the max heap property.
*/
private void remove() {
int max = maxHeap[START_IDX];
/**Put the last element on the TOP and Heapify it.*/
maxHeap[START_IDX] = maxHeap[size--];
maxHeapify(START_IDX);
System.out.println("Maximum element:"+max);
}
/**
* Heapify to get back Max-Heap.
* @param indx
*/
private void maxHeapify(int indx) {
if(!isLeaf(indx)) {
/** To check left and right child element.
* If greater then heapify. */
if(maxHeap[indx]<maxHeap[leftChild(indx)] ||
maxHeap[indx]<maxHeap[rightChild(indx)]) {
/** Heapify the left Max-Heap. */
if(maxHeap[indx]<maxHeap[leftChild(indx)]) {
swapElement(indx, leftChild(indx));
maxHeapify(leftChild(indx));
} else {
swapElement(indx, rightChild(indx));
maxHeapify(rightChild(indx));
}
}
}
}
/**
* Return parent index of child index.
* @param indx
* @return parent index.
*/
private int parent(int currIdx) {
return currIdx/2;
}
/**
* Return right child index.
* @param indx
* @return right child index.
*/
private int rightChild(int indx) {
return indx*2+1;
}
/**
* Return left child index.
* @param indx
* @return left child index.
*/
private int leftChild(int indx) {
return indx*2;
}
/**
* To check whether the index is leaf or not.
* @param indx
* @return boolean value.
*/
private boolean isLeaf(int indx) {
if (indx>=(size/2) && indx<=size) {
return true;
}
return false;
}
/**
* Utility to print the Max-Heap elements.
*/
private void printMaxHeap() {
for (int i = 1; i <= size / 2; i++ ) {
StringBuffer sb = new StringBuffer("Perent: "+maxHeap[i]);
if(size>=2*i) {
sb.append(" Left: "+ maxHeap[2*i]);
}
if(size>=2*i+1) {
sb.append(" Right:"+maxHeap[2*i+1]);
}
System.out.print(sb.toString());
System.out.println();
}
}
public static void main(String[] args) {
MaxHeap heap = new MaxHeap(10);
heap.insert(5);
heap.insert(3);
heap.insert(17);
heap.insert(10);
heap.insert(84);
heap.insert(19);
heap.insert(6);
heap.insert(22);
heap.insert(9);
heap.remove();
heap.printMaxHeap();
}
}
No comments:
Post a Comment