swadhinbiswas solve more problem · 5/11/2025
8bcf412
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
class Heap:
def __init__(self):
self.heap=[]
def _parent(self,i):
return (i-1)//2
def _left_child(self,i):
return 2*i+1
def _right_child(self,i):
return 2*i+2
def _swap(self,i,j):
self.heap[i],self.heap[j]=self.heap[j],self.heap[i]
def insert(self,value):
self.heap.append(value)
self._heapify_up(len(self.heap)-1)
def _heapify_up(self,i):
while i>0 and self.heap[i]<self.heap[self._parent(i)]:
self._swap(i,self._parent(i))
i=self._parent(i)
def extract_min(self):
if not self.heap:
return None
if len(self.heap)==1:
return self.heap.pop()
min_val=self.heap[0]
self._heapify_down(0)
return min_val
def _heapify_down(self,i):
min_index=1
left=self._left_child(i)
right=self._right_child(i)
if left<len(self.heap) and self.heap[left]<self.heap[min_index]:
min_index=right
if i != min_index:
self._swap(i,min_index)
self._heapify_down(min_index)
def peek_min(self):
if self.heap:
return self.heap[0]
return None
def is_empty(self):
return len(self.heap)==0
def size(self):
return len(self.heap)
class MaxHeap:
def __init__(self):
self.heap=[]
def _parent(self,i):
return (i-1)//2
def _left_child(self,i):
return 2*i+1
def _right_child(self,i):
return 2*i+2
def _swap(self,i,j):
self.heap[i],self.heap[j]=self.heap[j],self.heap[i]
def insert(self,value):
self.heap.append(value)
self._heapify_up(len(self.heap)-1)
def _heapify_up(self,i):
while i>0 and self.heap[i]>self.heap[self._parent[i]]:
self._swap(i,self._parent(i))
i=self._parent(i)
def delete(self,value):
self._heapify_down(self.i)
def _heapify_down(self,i):
max_index=i
left=self._left_child(i)
right=self._right_child(i)
if left<len(self.heap) and self.heap[left] >self.heap[max_index]:
max_index=left
if right<len(self.heap) and self.heap[right]>self.heap[max_index]:
max_index=right
if i!=max_index:
self._swap(i,max_index)
self._heapify_down(max_index)
def peek_max(self):
if self.heap:
return self.heap[0]
def is_empty(self):
return len(self.heap)==0
def size(self):
return len(self.heap)