link1
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// import java.util.Arrays;
// import java.util.NoSuchElementException;
class BinaryHeap {
private int[] heap;
private int capacity;
private int heapSize;
// This will initialize our heap with default size.
public BinaryHeap(int capacity) {
heapSize = 0;
this.capacity=capacity;
heap = new int[this.capacity];
Arrays.fill(heap, -1);
}
// This will check if the heap is empty or not Complexity: O(1)
public boolean isEmpty() {
return heapSize == 0;
}
// This will check if the heap is full or not Complexity: O(1)
public boolean isFull() {
return heapSize == heap.length;
}
private int parent(int i) {
return (i - 1) / 2;
}
// This method used to maintain the heap property while inserting an element.
private void heapifyUp(int i) {
int tmp = heap[i];
while (i > 0 && tmp > heap[parent(i)]) {
heap[i] = heap[parent(i)];
i = parent(i);
}
heap[i] = tmp;
}
// This will insert new element in to heap Complexity: O(log N) As worst case
// scenario, we need to traverse till the root
public void insert(int x) {
if (isFull()) throw new NoSuchElementException("Heap is full, No space to insert new element");
heap[heapSize++] = x;
heapifyUp(heapSize - 1);
}
public void heapifyDown(int i) {
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < heapSize && heap[l] > heap[largest]) largest = l;
// If right child is larger than largest so far
if (r < heapSize && heap[r] > heap[largest]) largest = r;
// If largest is not root
if (largest != i) {
int swap = heap[i];
heap[i] = heap[largest];
heap[largest] = swap;
// Recursively heapify the affected sub-tree
heapifyDown(largest);
}
}
// This will delete element at index idx Complexity: O(log N)
public int delete(int idx) {
if (isEmpty()) throw new NoSuchElementException("Heap is empty, No element to delete");
if (idx>=this.capacity) throw new ArrayIndexOutOfBoundsException("out of bounds for length "+this.capacity);
int key = heap[idx];
heap[idx] = heap[heapSize - 1];
heapSize--;
heapifyDown(idx);
return key;
}
// This method returns the max element of the heap. complexity: O(1)
public int findMax() {
if (isEmpty()) throw new NoSuchElementException("Heap is empty.");
return heap[0];
}
// This method used to print all element of the heap
public void printHeap() {
System.out.print(heapSize+"Heap = ");
for (int i = 0; i < heapSize; i++) System.out.print(heap[i] + " ");
System.out.println();
}
}
/*
public class MyClass2 {
public static void main(String[] args) {
BinaryHeap maxHeap = new BinaryHeap(10);
maxHeap.insert(10);
maxHeap.insert(4);
maxHeap.insert(9);
maxHeap.insert(1);
maxHeap.insert(7);
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.printHeap();
maxHeap.delete(9);
maxHeap.printHeap();
}
}*/