Repository navigation
Expand file tree
/
Copy path堆排序.py
More file actions
69 lines (55 loc) · 1.75 KB
/
Copy path堆排序.py
File metadata and controls
69 lines (55 loc) · 1.75 KB
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
class Heap:
def __init__(self, max_count):
self.max_count = max_count
self.count = 0
self.heap = [0]
# 大顶堆的插入
def insert_data_to_heap(self, data):
if len(self.heap) > self.max_count:
return
self.count += 1
self.heap.append(data)
i = self.count
while i > 0:
if i // 2 > 0 and self.heap[i] > self.heap[i // 2]:
temp = self.heap[i]
self.heap[i] = self.heap[i // 2]
self.heap[i // 2] = temp
i = i // 2
else:
break
# 自顶向下的堆化
def heaify(self):
index = 1
while True:
max_value = self.heap[index]
max_index = index
if index * 2 > self.count or index * 2 + 1 > self.count:
break
if max_value < self.heap[index * 2]:
max_value = self.heap[index * 2]
max_index = index * 2
if max_value < self.heap[index * 2 + 1]:
max_value = self.heap[index * 2 + 1]
max_index = index * 2 + 1
if max_index == index:
break
else:
temp = self.heap[index]
self.heap[index] = max_value
self.heap[max_index] = temp
index = max_index
def remove_top_data(self):
count = len(self.heap)
self.heap[1] = self.heap[count -1]
self.count -= 1
self.heaify()
def print_data(self):
print(self.heap)
test_array = [5,6,7,8,1,2,9,16,13,15,22,27,21,33]
heap = Heap(20)
for value in test_array:
heap.insert_data_to_heap(value)
heap.print_data()
heap.remove_top_data()
heap.print_data()