8000 Heaps · harshspandey1/DSA-Bootcamp-Java@53d6807 · GitHub
[go: up one dir, main page]
Skip to content

Commit 53d6807

Browse files
kunal-kushwahakunal-kushwaha
authored
Heaps
1 parent 74bd464 commit 53d6807

File tree

3 files changed

+102
-0
lines changed

3 files changed

+102
-0
lines changed

‎lectures/24-heaps/code/heaps-1/Heap.java

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
import java.util.ArrayList;
2+
3+
class Heap<T extends Comparable<T>> {
4+
5+
private ArrayList<T> list;
6+
7+
public Heap() {
8+
list = new ArrayList<>();
9+
}
10+
11+
private void swap(int first, int second) {
12+
T temp = list.get(first);
13+
list.set(first, list.get(second));
14+
list.set(second, temp);
15+
}
16+
17+
private int parent(int index) {
18+
return (index - 1) / 2;
19+
}
20+
21+
private int left(int index) {
22+
return index * 2 + 1;
23+
}
24+
25+
private int right(int index) {
26+
return index * 2 + 2;
27+
}
28+
29+
public void insert(T value) {
30+
list.add(value);
31+
upheap(list.size() - 1);
32+
}
33+
private void upheap(int index) {
34+
if(index == 0) {
35+
return;
36+
}
37+
int p = parent(index);
38+
if(list.get(index).compareTo(list.get(p)) < 0) {
39+
swap(index, p);
40+
upheap(p);
41+
}
42+
}
43+
44+
public T remove() throws Exception {
45+
if (list.isEmpty()) {
46+
throw new Exception("Removing from an empty heap!");
47+
}
48+
49+
T temp = list.get(0);
50+
51+
T last = list.remove(list.size() - 1);
52+
if (!list.isEmpty()) {
53+
list.set(0, last);
54+
downheap(0);
55+
}
56+
57+
return temp;
58+
}
59+
private void downheap(int index) {
60+
int min = index;
61+
int left = left(index);
62+
int right = right(index);
63+
64+
if(left < list.size() && list.get(min).compareTo(list.get(left)) > 0) {
65+
min = left;
66+
}
67+
68+
if(right < list.size() && list.get(min).compareTo(list.get(right)) > 0) {
69+
min = right;
70+
}
71+
72+
if(min != index) {
73+
swap(min, index);
74+
downheap(min);
75+
}
76+
}
77+
78+
public ArrayList<T> heapSort() throws Exception {
79+
ArrayList<T> data = new ArrayList<>();
80+
while(!list.isEmpty()) {
81+
data.add(this.remove());
82+
}
83+
return data;
84+
}
85+
}

‎lectures/24-heaps/code/heaps-1/Main.java

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
import java.util.ArrayList;
2+
3+
class Main {
4+
public static void main(String[] args) throws Exception{
5+
Heap<Integer> heap = new Heap<>();
6+
7+
heap.insert(34);
8+
heap.insert(45);
9+
heap.insert(22);
10+
heap.insert(89);
11+
heap.insert(76);
12+
13+
ArrayList list = heap.heapSort();
14+
System.out.println(list);
15+
16+
}
17+
}

‎lectures/24-heaps/notes/Heaps - 1.pdf

1.04 MB
Binary file not shown.

0 commit comments

Comments
 (0)
0