Binary Heap Coding

HeapByArray.java

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
package com.chung;

public class HeapByArray {
	int[] arr;
	int sizeOfTree;
	
	
	//Constructor
	public HeapByArray(int size) {
		//We are adding 1 here so that first cell of the array can be left blank all the time. This is eliminate problem of array starting from index 0.
		arr = new int[size+1];
		this.sizeOfTree = 0;
		System.out.println("Empty Heap has been created !");
	}//end of method

	
	public int sizeOfArray() {
		return arr.length;
	}
	
	
	public int sizeOfTree() {
		System.out.println("Size Of Tree: " + sizeOfTree);
		return sizeOfTree;
	}//end of method
	
	
	
	public boolean isHeapEmpty() {
		if (sizeOfTree <= 0) {
			System.out.println("Tree is empty !");
			return true;
		}else {
			System.out.println("Tree is not empty !");
			return false;
		}
	}//end of method
	
	
	
	public void deleteheap() {
		arr = null;
		System.out.println("Heap has been deleted !");
	}//end of method
	
	
	
	//Insert a new value in Heap
	public void insertInHeap(int value) {
		//Doing +1 because sizeOfTree always points to the last occupied cell of the array 
		System.out.println("Inserting " + value + " in Heap...");
		arr[sizeOfTree+1] = value;
		sizeOfTree++;
		HeapifyBottomToTop(sizeOfTree);
		System.out.println("Inserted " + value + " successfully in Heap !");
		levelOrder();
	}//end of method
	
	
	
	// Peek into Heap
	public void peek() {
		if(sizeOfTree == 0) {
			System.out.println("Heap is empty !");
		}else {
			System.out.println("Head of the Heap is: " + arr[1]);
		}
	}//end of method
	
	
	
	//Extract Head of Heap
	public int extractHeadOfHeap() {
		if(sizeOfTree == 0) {
			System.out.println("Heap is empty !");
			return -1;
		}else {
			System.out.println("Head of the Heap is: " + arr[1]);
			System.out.println("Extracting it now...");
			int extractedValue = arr[1];
			arr[1] = arr[sizeOfTree];
			sizeOfTree--;
			HeapifyTopToBottom(1);
			System.out.println("Successfully extracted value from Heap.");
			levelOrder();
			return extractedValue;
		}
	}//end of method
	

	
	
	public void HeapifyBottomToTop(int index) {
		int parent = index / 2;
		// We are at root of the tree. Hence no more Heapifying is required.
		if (index <= 1) {
			return;
		}
		// If Current value is smaller than its parent, then we need to swap
		if (arr[index] < arr[parent]) {
			int tmp = arr[index];
			arr[index] = arr[parent];
			arr[parent] = tmp;
		}
		HeapifyBottomToTop(parent);
	}//end of method
	
	
	
	
	public void HeapifyTopToBottom(int index) {
		int left  = index*2;
		int right = (index*2)+1;
		int smallestChild = 0;
		
		if (sizeOfTree < left) { //If there is no child of this node, then nothing to do. Just return.
			return; 
		}else if (sizeOfTree == left) { //If there is only left child of this node, then do a comparison and return.
			if(arr[index] > arr[left]) {
				int tmp = arr[index];
				arr[index] = arr[left];
				arr[left] = tmp;
			}
			return;
		}else { //If both children are there
			if(arr[left] < arr[right]) { //Find out the smallest child
				smallestChild = left;
			}else {
				smallestChild = right;
			}
			if(arr[index] > arr[smallestChild]) { //If Parent is greater than smallest child, then swap
				int tmp = arr[index];
				arr[index] = arr[smallestChild];
				arr[smallestChild] = tmp;
			}
		}
		HeapifyTopToBottom(smallestChild);
	}//end of method
	
	
	
	public void levelOrder() {
		System.out.println("Printing all the elements of this Heap...");// Printing from 1 because 0th cell is dummy
		for (int i = 1; i <= sizeOfTree; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println("\n");
	}//end of method
	
	
}//end of class

출처 : “Data Structures & Algorithms” by DS GUY