Lab 09 Min Heap of Integers! Objective: Implement a minimum (min) heap of intege
ID: 3680942 • Letter: L
Question
Lab 09
Min Heap of Integers!
Objective:
Implement a minimum (min) heap of integers, and write a driver to demonstrate its functionality. Min heaps work the same way as maximum (max) heaps except the a parent is always smaller than its children.
The class your min heap should have the following methods
insert: Add a new element to the heap, and bubble up as needed.
delete: Remove the first element from the heap and then reheapify.
heapSort: Make a copy of the heap, then remove and print each element from the clone. Make sure this doesn’t modify the current heap.
print: Prints the elements in the heap in breadth order.
Example Print Out:
Int Min Heap Tester
Populating Heap with values
21
37
49
11
23
1
13
16
33
17
Printing Heap
1
16
11
21
17
49
13
37
33
23
Testing heap sort
1 11 13 16 17 21 23 33 37 49
Removing an element from the heap
The element removed is 1 and the heap now is:
11
16
13
21
17
49
23
37
33
Explanation / Answer
Java code to insert an element into a heap
public class BinaryMinHeap {
…
public void insert(int value) {
if (heapSize == data.length)
throw new HeapException("Heap's underlying storage is overflow");
else {
heapSize++;
data[heapSize - 1] = value;
siftUp(heapSize - 1);
}
}
…
private void siftUp(int nodeIndex) {
int parentIndex, tmp;
if (nodeIndex != 0) {
parentIndex = getParentIndex(nodeIndex);
if (data[parentIndex] > data[nodeIndex]) {
tmp = data[parentIndex];
data[parentIndex] = data[nodeIndex];
data[nodeIndex] = tmp;
siftUp(parentIndex);
}
}
}
}
Java code to remove the minimum from a heap
public class BinaryMinHeap {
…
public void removeMin() {
if (isEmpty())
throw new HeapException("Heap is empty");
else {
data[0] = data[heapSize - 1];
heapSize--;
if (heapSize > 0)
siftDown(0);
}
}
…
private void siftDown(int nodeIndex) {
int leftChildIndex, rightChildIndex, minIndex, tmp;
leftChildIndex = getLeftChildIndex(nodeIndex);
rightChildIndex = getRightChildIndex(nodeIndex);
if (rightChildIndex >= heapSize) {
if (leftChildIndex >= heapSize)
return;
else
minIndex = leftChildIndex;
} else {
if (data[leftChildIndex] <= data[rightChildIndex])
minIndex = leftChildIndex;
else
minIndex = rightChildIndex;
}
if (data[nodeIndex] > data[minIndex]) {
tmp = data[minIndex];
data[minIndex] = data[nodeIndex];
data[nodeIndex] = tmp;
siftDown(minIndex);
}
}
}
Sample code for min-heap
public class minHeap {
public int size;
public int [] mH;
public int position;
public minHeap(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){
if(position==0){
mH[position+1]=x;
position = 2;
}else{
mH[position++]=x;
bubbleUp();
}
}
public void bubbleUp(){
int pos = position-1;
while(pos>0 && mH[pos/2]>mH[pos]){
int y = mH[pos];
mH[pos]=mH[pos/2];
mH[pos/2] = y;
pos = pos/2;
}
}
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 a = mH[k];
int smallest =k;
if(2*k<position && mH[smallest]>mH[2*k]){
smallest = 2*k;
}
if(2*k+1<position && mH[smallest]>mH[2*k+1]){
smallest = 2*k+1;
}
if(smallest!=k){
swap(k,smallest);
sinkDown(smallest);
}
}
public void swap(int a, int b){
//System.out.println("swappinh" + mH[a] + " and " + mH[b]);
int temp = mH[a];
mH[a] = mH[b];
mH[b] = temp;
}
public static void main(String args[]){
int arrA [] = {3,2,1,7,8,4,10,16,12};
System.out.print("Original Array : ");
for(int i=0;i<arrA.length;i++){
System.out.print(" " + arrA[i]);
}
minHeap m = new minHeap(arrA.length);
System.out.print(" Min-Heap : ");
m.createHeap(arrA);
m.display();
System.out.print("Extract Min :");
for(int i=0;i<arrA.length;i++){
System.out.print(" " + m.extractMin());
}
}
}
note-by using or modifying the above code samples program for the given question can be done.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.