AlgorithmsAndDataStructures/Heap.java at master · biprade/AlgorithmsAndDataStructures · 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

public class Heap {
	static int[] input={3,1,2,6,5,4,8};
public static void main(String[] args){

//	getMaxHeap(input);
//	for(int i=0;i<input.length;i++)
//		System.out.println(input[i]);

	getMinHeap(input);
	for(int i=0;i<input.length;i++)
		System.out.println(input[i]);
}

static void getMaxHeap(int[] inp){
	int lastRootIndex=(inp.length/2)-1;
	for(int i=lastRootIndex;i>=0;i--){
		maxHeapify(i);
	}
}
static void maxHeapify(int index){
	if(!(input[index]>input[2*index+1] && input[index]>input[2*index+2])){
		if(input[2*index+1]>input[2*index+2]){
			swap(index,2*index+1);
			if(2*index+1<=(input.length/2)-1)
				maxHeapify(2*index+1);
		}
		else{
			swap(index,2*index+2);
			if(2*index+2<=(input.length/2)-1)
				maxHeapify(2*index+2);
		}
		//heapify(index);
	}
	else
		return;
}
static void swap(int index,int childIndex){
	int temp=input[index];
	input[index]=input[childIndex];
	input[childIndex]=temp;
}


static void getMinHeap(int[] inp){
	int lastRootIndex=(inp.length/2)-1;
	for(int i=lastRootIndex;i>=0;i--){
		minHeapify(i);
	}
}
static void minHeapify(int index){
	if(!(input[index]<input[2*index+1] && input[index]<input[2*index+2])){
		if(input[2*index+1]<input[2*index+2]){
			swap(index,2*index+1);
			if(2*index+1<=(input.length/2)-1)
				minHeapify(2*index+1);
		}
		else{
			swap(index,2*index+2);
			if(2*index+2<=(input.length/2)-1)
				minHeapify(2*index+2);
		}
		//heapify(index);
	}
	else
		return;
}
}