发布于 

堆| 笔记整理!

堆| 笔记整理!

思路梳理 | 结构体部分

1
2
3
def __init__(self) -> None:
   self.heap_list=[0]
   self.length=0

主体部分是 | 上升和下降

上升部分 | 对应的是 插入

1
2
3
4
5
6
7
8
9
10
11
def perc_up(self,i):
   while i//2>0:
	  # 当前节点是 小于父节点的
	  if self.heap_list[i]<self.heap_list[i//2]:
		 self.heap_list[i],self.heap_list[i//2]=self.heap_list[i//2],self.heap_list[i]
	  i>>=1

def insert(self,k):
   self.heap_list.append(k)
   self.length+=1
   self.perc_up(self.length)

下降部分 | 对应的是建立 + 删除堆顶元素

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
def perc_down(self,i):
   while i*2<=self.length:
	  idx=self.min_child(i)
	  if self.heap_list[i]>self.heap_list[idx]:
		 self.heap_list[i],self.heap_list[idx]=self.heap_list[idx],self.heap_list[i]
	  i=idx
    
def min_child(self,i):
   if i*2+1>self.length:
	  return i*2
   else:
	  if self.heap_list[i*2]<self.heap_list[i*2+1]:
		 return i*2
	  return i*2+1
    
def del_min(self):
   min_val=self.heap_list[1]
   # self.heap_list[1]=self.heap_list[self.length] # 这样来写也可以id self.heap_list[-1]
   self.heap_list[1]=self.heap_list.pop()
   self.length-=1
   self.perc_down(1)
   return min_val
    
def build_heap(self,ls):
   self.length=len(ls)
   i=self.length//2
   self.heap_list=[0]+ls[:]
   while i>0:
	  self.perc_down(i)
	  i-=1

完整代码 | 关于最大堆+最小堆

最大堆

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
class BinaryHeap():
	def __init__(self):
		self.heap_list=[0]
		self.length=0

	def insert(self,i):
		self.heap_list.append(i)
		self.length+=1
		self.perc_up(self.length)

	def perc_up(self,i):
		while i//2>0:
			if self.heap_list[i]>self.heap_list[i//2]:
				self.heap_list[i],self.heap_list[i//2]=self.heap_list[i//2],self.heap_list[i]
			i>>=1

	def max_child(self,i):
		if i*2+1>self.length:
			return i*2
		else:
			if self.heap_list[i*2]>self.heap_list[i*2+1]:
				return i*2
			return i*2+1

	def del_max(self,i):
		val=self.heap_list[1]
		self.heap_list[1]=self.heap_list.pop()
		self.length-=1
		self.perc_down(1)
		return val

	def perc_down(self,i):
		while i*2<=self.length:
			idx=self.max_child(i)
			if self.heap_list[i]<self.heap_list[idx]:
				self.heap_list[i],self.heap_list[idx]=self.heap_list[idx],self.heap_list[i]
			i=idx

	def build_heap(self,ls):
		self.length=len(ls)
		i=self.length//2
		self.heap_list=[0]+ls[:]
		while i>0:
			self.perc_down(i)
			i-=1

if __name__=='__main__':
	ls=[9,5,6,3,2,3,10]
	heap=BinaryHeap()
	heap.build_heap(ls)
	print(heap.heap_list)

最小堆

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
class BinaryHeap():
    def __init__(self) -> None:
        self.heap_list=[0]
        self.length=0

    def perc_up(self,i):
        while i//2>0:
            # 当前节点是 小于父节点的
            if self.heap_list[i]<self.heap_list[i//2]:
                self.heap_list[i],self.heap_list[i//2]=self.heap_list[i//2],self.heap_list[i]
            i>>=1
    
    def insert(self,k):
        self.heap_list.append(k)
        self.length+=1
        self.perc_up(self.length)

    def perc_down(self,i):
        while i*2<=self.length:
            idx=self.min_child(i)
            if self.heap_list[i]>self.heap_list[idx]:
                self.heap_list[i],self.heap_list[idx]=self.heap_list[idx],self.heap_list[i]
            i=idx
    
    def min_child(self,i):
        if i*2+1>self.length:
            return i*2
        else:
            if self.heap_list[i*2]<self.heap_list[i*2+1]:
                return i*2
            return i*2+1
    
    def del_min(self):
        min_val=self.heap_list[1]
        # self.heap_list[1]=self.heap_list[self.length] # 这样来写也可以id self.heap_list[-1]
        self.heap_list[1]=self.heap_list.pop()
        self.length-=1
        self.perc_down(1)
        return min_val
    
    def build_heap(self,ls):
        self.length=len(ls)
        i=self.length//2
        self.heap_list=[0]+ls[:]
        while i>0:
            self.perc_down(i)
            i-=1

if __name__=='__main__':
    ls=[9,6,5,2,3]
    heap=BinaryHeap()
    heap.build_heap(ls)
    print(heap.heap_list)
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧