Learn-dsa..in 30 days!



























CC-1 : Implement Max Heap.

Description:

In below sections we will code a custom Binary Max Heap using array. The insert() method of the Heap will add the node at the appropriate level and position is the maxHeap and the delete() method will remove root node from the Binary Tree. We will use an array to store the individual data of the nodes, the indexes of the nodes will indicate the parent – child relations of the nodes as described below:

For each node at index idx, its left child will be stored at index ((2*idx)+1)) and right child will be stored at index ((2*idx)+2).

Test cases and expected outputs:

Input Parameters Expected outputs
HeapMax hp=new HeapMax();
hp.insert(43);
hp.insert(92);
hp.insert(21);
hp.insert(44);
hp.insert(12);
hp.insert(67);
hp.insert(55);
retVal=hp.getMaxHeap();
printArray(retVal, "Max Heap"); 		Max Heap :
[0] = 92
[1] = 44
[2] = 67
[3] = 43
[4] = 12
[5] = 21
[6] = 55
hp.deleteTop();
retVal=hp.getMaxHeap();
printArray(retVal, "Max Heap after top deletion");
 Max Heap after top deletion :
[0] = 67
[1] = 44
[2] = 55
[3] = 43
[4] = 12
[5] = 21

Next let’s see the logic involved in adding/ deleting nodes from Heap.

Addition of node to Heap.

Pseudocode:

To handle addition of a new node to a Heap, we need to implement following steps:
Use array to store heap nodes data and structure. The Heap structure’s parent child relationships will be managed using array indices as described in section above.
Use int variable currSize to track the size of the heap.
Add the new node to the index currSize+1.
Repeat below steps till new node’s data is greater than its parent data:
o Swap new node’s (child’s) node data and its current parent node’s node data.

Code:

public class HeapMax {
 
private int[] maxHeap=new int[20];
private int currSize;
	
public boolean insert(int num) {
	if (currSize >= maxHeap.length) {return false;}
	maxHeap[currSize]=num;
	currSize++;
	int idx=currSize-1;
	int parentIdx=(idx-1)/2;
	while ((idx > 0)&& (maxHeap[idx]> maxHeap[parentIdx])){
		int temp=maxHeap[idx];
		maxHeap[idx]=maxHeap[parentIdx];
		maxHeap[parentIdx]=temp;
		idx=parentIdx;
		parentIdx=(idx-1)/2;
	}
	
	return true;
}
}

Deletion of node from Heap.

Pseudocode:

The node data of the node to be deleted is received as input by delete method.
We will use this node data to search the index in array that’s value need to be deleted from the Heap.
Once we have identified the index idx at which the data to be deleted is present, interchange the node data at index (currSize-1) and idx.
Now call updateHeap() (also known as heapify()) method to re-arrange the tree as per Max Heap properties.

Code:

public class HeapMax {
 
private int[] maxHeap=new int[20];
private int currSize;

public int delete(int val) {
	if (currSize == 0) {return Integer.MIN_VALUE;}
	int idx=-1;
	for (int i=0;i < currSize; i++) {
		if (maxHeap[i]==val) {
			idx=i;			
		}
	}
	if (idx==-1) {return Integer.MIN_VALUE;}
	maxHeap[idx]=maxHeap[currSize-1];
	maxHeap[currSize-1]=0;
	currSize--;
	updateHeap(idx);
	return idx;
}

UpdateHeap() (also known as Heapify() method).

Pseudocode:

This method takes index idx of heap array as input variable.
It moves the node data at index idx to its correct position in the Max Heap.
If node data at left child index of idx or right child index of idx is greater than node data at index idx:
Node data at index idx and its child index childIdx with greater node data is swapped.
UpdateHeap() is recursively called with the index of the child childIdx .

Code:

public void updateHeap(int idx) {
	int parentIdx=idx;
	int leftChildIdx= 2*idx+1;
	int rightChildIdx=2*idx+2;
	if ((leftChildIdx < currSize) && (maxHeap[leftChildIdx] > maxHeap [parentIdx])) {
		parentIdx=leftChildIdx;
	}
	if ((rightChildIdx < currSize) && (maxHeap[rightChildIdx] > maxHeap [parentIdx])) {
		parentIdx=rightChildIdx;
	}
	if (parentIdx != idx) {
		int temp=maxHeap[idx];
		maxHeap[idx]=maxHeap[parentIdx];
		maxHeap[parentIdx]=temp;
		updateHeap(parentIdx);
	}
}

Deletion of top node from Heap.

Pseudocode:

To handle deletion of top node of a Heap, we implement following steps:
Interchange the node data at index (currSize-1) and 0.
Now call updateHeap() (also known as heapify()) method to re-arrange the tree as per Max Heap properties.

Code:

public int deleteTop() {
	if (currSize == 0) {return Integer.MIN_VALUE;}
	int top=maxHeap[0];
	maxHeap[0]=maxHeap[currSize-1];
	maxHeap[currSize-1]=0;
	currSize--;
	updateHeap(0);
	
	return top;
}

Traversing the nodes of a Heap.

Since heap is stored in an Array, the Max Heap can be traversed easily using array Indexes. Remember that for each node at index idx, Its left child will be stored at index ((2*idx)+1)) and right child will be stored at index ((2*idx)+2).

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us