DataStructureImplementation/MyMinHeap1.java at main · Sankeerth10/DataStructureImplementation · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.util.Scanner;

class Heap1{
	private int [] heapArr;
	int currentSize;

	public Heap1() {
		this.heapArr= new int[10000];
		this.currentSize = 0;
	}

	public void add(int val) {
		if(currentSize==0) {
			heapArr[currentSize] = val;
			currentSize++;
		}
		else {
			heapArr[currentSize] = val;
			upHeap(currentSize);
			currentSize++;
		}
	}

	public void upHeap(int index) {
		int parentIndex = ((index-1)/2);
		if(heapArr[parentIndex]> heapArr[index]) {
			int temp = heapArr[parentIndex];
			heapArr[parentIndex] =heapArr[index];
			heapArr[index] = temp;
			upHeap(parentIndex);
		}
		return;
	}

	public int removeMin() {
		int minimumElement = heapArr[0];
		int lastElement = currentSize-1;
		heapArr[0] = heapArr[lastElement];
		System.out.println("last element: " + heapArr[0]);
		heapArr[lastElement] = 0;
		currentSize--;
		downHeap(0);
		return minimumElement;
	}

	public void downHeap(int index) {
		int leftChildIndex = (2*index)+1;
		int rightChildIndex = (2*index)+2;
		if(currentSize-1<leftChildIndex) {
			return;
		}
		else if(currentSize-1 == leftChildIndex) {
			if(heapArr[leftChildIndex] < heapArr[index]) {
				int temp = heapArr[leftChildIndex];
				heapArr[leftChildIndex] = heapArr[index];
				heapArr[index] = temp;
				downHeap(leftChildIndex);
			}
	}else {
		int indexToSwap=0;
		System.out.println("lc "+ heapArr[leftChildIndex]);
		System.out.println("rc " + heapArr[rightChildIndex]);
		if(heapArr[leftChildIndex]<heapArr[rightChildIndex]) {
			indexToSwap = leftChildIndex;
		}
		else {
			indexToSwap = rightChildIndex;
		}
		if(heapArr[index]>heapArr[indexToSwap]) {
			int temp = heapArr[index];
			heapArr[index] = heapArr[indexToSwap];
			heapArr[indexToSwap] = temp;
			downHeap(indexToSwap);
		}
				}
	}
	public boolean isHeapEmpty() {
		return currentSize==-1;
	}

	public void printHeap() {
		for(int i=0; i<=currentSize-1;i++) {
			System.out.println(heapArr[i]);
		}
	}
}

public class MyMinHeap1 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Heap1 heap = new Heap1();
		int valueToAdd = sc.nextInt();
		heap.add(valueToAdd);
		int valueToAdd1 = sc.nextInt();
		heap.add(valueToAdd1);
		int valueToAdd2 = sc.nextInt();
		heap.add(valueToAdd2);
		int valueToAdd3 = sc.nextInt();
		heap.add(valueToAdd3);
		System.out.print("HEAP AFTER ADD: ");
		heap.printHeap();

		System.out.println("Min: " + heap.removeMin());
		System.out.print("HEAP AFTER REMOVE: ");
		heap.printHeap();
		System.out.println("Min: " + heap.removeMin());
		System.out.print("HEAP AFTER REMOVE: ");
		heap.printHeap();

	}

}