-
Notifications
You must be signed in to change notification settings - Fork 1
/
最大堆.py
94 lines (82 loc) · 2.5 KB
/
最大堆.py
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
# -*- coding:UTF-8 -*-
class MaxHeap():
'''最大堆的实现'''
def __init__(self):
'''初始化-使用列表实现'''
self.heaplist = [0]
self.heaphigh = 0
def insert(self,data):
'''插入元素'''
self.heaplist.append(data)
self._dataUp()
self.heaphigh += 1
print(self.heaplist, self.heaphigh)
def _dataUp(self):
'''插入元素-上浮操作'''
high = len(self.heaplist)-1
while high > 1 :
index = high // 2
if self.heaplist[high] > self.heaplist[index]:
self.heaplist[high],self.heaplist[index] = self.heaplist[index], self.heaplist[high]
high = index
return self.heaplist
def del_max(self):
'''删除最大值'''
self._dataDown()
self.heaplist.pop()
self.heaphigh -= 1
print(self.heaplist,self.heaphigh)
def _dataDown(self):
'''删除元素-下沉操作'''
index = 1
high = len(self.heaplist)
data = self.heaplist[-1]
while 2*index+1 < high:
if self.heaplist[2*index] > self.heaplist[2*index+1]:
if self.heaplist[2*index] > data:
self.heaplist[index],self.heaplist[2*index] = self.heaplist[2*index],data
index *= 2
else:
return self.heaplist
else:
if self.heaplist[2*index+1] > data:
self.heaplist[index],self.heaplist[2*index+1] = self.heaplist[2*index+1],data
index = 2*index+1
else:
return self.heaplist
@property
def find_max(self):
'''返回最大元素'''
return None if self.heaphigh == 0 else self.heaplist[1]
@property
def is_empty(self):
return True if self.heaphigh == 0 else False
@property
def size(self):
'''返回长度'''
return None if self.heaphigh == 0 else self.heaphigh
if __name__ == '__main__':
heap = MaxHeap()
heap.insert(100)
heap.insert(90)
heap.insert(85)
heap.insert(80)
heap.insert(30)
heap.insert(60)
heap.insert(50)
heap.insert(55)
heap.insert(1010)
heap.insert(10000)
heap.insert(1)
print(heap.find_max)
print(heap.is_empty)
print(heap.size)
heap.del_max()
heap.del_max()
heap.del_max()
heap.del_max()
heap.del_max()
heap.del_max()
print(heap.find_max)
print(heap.is_empty)
print(heap.size)