Max Heap - Insert and Extract All Max Element

MaxHeap.java

// the implementation uses 1 as the root and not 1. So the left, right and root will be - 2i, 2i+1, i/2 respectively.

class MaxHeap {
	public int size;
	public int[] mH;
	public int position;

	public MaxHeap(int size) 
	{
		this.size = size;
		mH = new int[size + 1];
		position = 0;
	}

	public void createHeap(int[] arrA) {
		if (arrA.length > 0) {
			for (int i = 0; i < arrA.length; i++) {
				insert(arrA[i]);
			}
		}
	}

	public void display() {
		for (int i = 1; i < mH.length; i++) {
			System.out.print(" " + mH[i]);
		}
		System.out.println("");
	}

	public void insert(int x) {
		// this root element is set as 1 and not 0. 
		// https://stackoverflow.com/questions/22900388/why-in-a-heap-implemented-by-array-the-index-0-is-left-unused/35460725#35460725
		if (position == 0) {
			mH[position + 1] = x;
			position = 2;
		} else {
			mH[position++] = x;
			bubbleUp();
		}
	}

	public void bubbleUp() 
	{
		int pos = position - 1;
		
		// We get the index of the last element. Then compare it with it's parent which is index/2
		// pos > 0 to check that position is still valid
		// if the parent is smaller than swap it 
		// next we set the pointer to the parent
		// we keep bubbling up until the particular element is at correct position 
		while (pos > 0 && pos/2 > 0 && mH[pos / 2] < mH[pos]) {
			int y = mH[pos];
			mH[pos] = mH[pos / 2];
			mH[pos / 2] = y;
			pos = pos / 2; // set the new pointer to point to the parent
		}
	}
	
	// maximum element is the first element. we will return that.
	// next we place the last element to that first position and then start the bubbling down 
	public int extractMin() {
		int min = mH[1];
		mH[1] = mH[position - 1];
		mH[position - 1] = 0;
		position--;
		sinkDown(1);
		return min;
	}

	public void sinkDown(int k) {
		int largest = k;
		// check if the index passed is greater than the left child.
		if ((2 * k) < position && mH[largest] < mH[2 * k]) {
			largest = 2 * k;
		}
		// check if the index passed is greater than the right child.
		if ((2 * k + 1) < position && mH[largest] < mH[2 * k + 1]) {
			largest = 2 * k + 1;
		}
		// if the current node satisfies the heap property then no need to change anything.
		// else swap and call bubble down with the new swapped node
		if (largest != k) {
			swap(k, largest);
			sinkDown(largest);
		}
    }

	public void swap(int a, int b) {
		int temp = mH[a];
		mH[a] = mH[b];
		mH[b] = temp;
	}

	public static void main(String args[]) {
		int arrA[] = { 10, 5, 6, 2, 12, 7, 9  };
		System.out.println("Original Array : ");
		for (int i = 0; i < arrA.length; i++) {
			System.out.print("  " + arrA[i]);
		}
		MaxHeap m = new MaxHeap(arrA.length);
		System.out.println("\nMin-Heap : ");
		m.createHeap(arrA);
		m.display();
		System.out.print("Extract Max :");
		for (int i = 0; i < arrA.length; i++) {
			System.out.print("  " + m.extractMin());
		}
	}
}