forked from Peefy/IntroductionToAlgorithm.Python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathchapter6_2.py
More file actions
123 lines (114 loc) · 4.63 KB
/
chapter6_2.py
File metadata and controls
123 lines (114 loc) · 4.63 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
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# python src/chapter6/chapter6_2.py
# python3 src/chapter6/chapter6_2.py
from __future__ import division, absolute_import, print_function
import sys as _sys
import math as _math
import random as _random
import time as _time
from random import randint as _randint
from copy import copy as _copy, deepcopy as _deepcopy
from numpy import arange as _arange
if __name__ == '__main__':
import heap
else:
from . import heap
class Chapter6_2:
'''
CLRS 第六章 6.2 算法函数和笔记
'''
def maxheapify(self, A, i):
'''
保持堆:使某一个结点i成为最大堆(其子树本身已经为最大堆)
'''
l = heap.left(i)
r = heap.right(i)
largest = 0
if l <= heap.heapsize(A) and A[l] >= A[i]:
largest = l
else:
largest = i
if r <= heap.heapsize(A) and A[r] >= A[largest]:
largest = r
if largest != i:
A[i], A[largest] = A[largest], A[i]
self.maxheapify(A, largest)
return A
def maxheapify_quick(self, A, i):
'''
保持堆:使某一个结点i成为最大堆(其子树本身已经为最大堆)
'''
count = len(A)
largest = count
while largest != i:
l = heap.left(i)
r = heap.right(i)
if l <= heap.heapsize(A) and A[l] >= A[i]:
largest = l
else:
largest = i
if r <= heap.heapsize(A) and A[r] >= A[largest]:
largest = r
if largest != i:
A[i], A[largest] = A[largest], A[i]
i, largest = largest, count
return A
def minheapify(self, A, i):
'''
保持堆:使某一个结点i成为最小堆(其子树本身已经为最小堆)
'''
l = heap.left(i)
r = heap.right(i)
minest = 0
if l <= heap.heapsize(A) and A[l] <= A[i]:
minest = l
else:
minest = i
if r <= heap.heapsize(A) and A[r] <= A[minest]:
minest = r
if minest != i:
A[i], A[minest] = A[minest], A[i]
self.minheapify(A, minest)
return A
def note(self):
'''
Summary
=
Print chapter6.2 note
Example
=
>>> Chapter6_2().note()
'''
print('6.2 保持堆的性质')
print('Max-heapify是对最大堆操作重要的子程序')
print('其输入是一个数组A和一个下标i')
print('假定以Left(i)和Right(i)为根的两颗二叉树都是最大堆，但是这是A[i]可能小于其子女，这样就违反了最大堆的性质')
print('Max-heapify的过程就是使A[i]下降，使以i为根的子树成为最大堆')
print('在算法Max-heapify的每一步里，从元素A[i], A[Left[i]], A[Right[i]]找出最大的的下标索引并存在largest中')
print('如果A[i]已经是最大的，则以i为根的子树已经是最大堆')
print('以该结点为根的子树又有可能违反最大堆性质，因而又要对该子树递归调用Max-heapify')
print('Max-heapify的运行时间T(n)<=T(2n/3)+Θ(1)')
print('根据主定理，该递归式的解为T(n)=O(lgn)')
print('或者说，Max-heapify作用于一个高度为h的结点所需要的运行时间为O(h)')
A = [25, 33, 15, 26, 22, 14, 16]
self.maxheapify(A, 0)
print('MaxHeapify的一个举例[25,33,15,26,22,14,16]，树的高度为3:', A)
A = [27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4,8, 9, 0]
print('练习6.2-1：在题中索引为3的元素(pyhton中索引为2)为3，写出二叉堆后要使其成为最大堆，',
'则3和10互换后再和8互换',
self.maxheapify(A, 2))
print('练习6.2-2:最小堆的一个例子[3,2,4,11,12,13,14]',
self.minheapify([3, 2, 4, 11, 12, 13, 14], 0))
print(' 感觉最大堆保持和最小堆没有区别啊，运行时间一致，只是不等号方向不同')
print('练习6.2-3，没效果吧，比如[7,6,5,4,3,2,1]:',self.maxheapify([7,6,5,4,3,2,1],0))
print('练习6.2-4,没效果吧')
A = [25, 33, 15, 26, 22, 14, 16]
print('练习6.2-5:[25, 33, 15, 26, 22, 14, 16],', self.maxheapify_quick(A, 0))
print('练习6.2-6 因为二叉堆树的高度就是lgn，所以最差情况就是遍历了整个二叉堆，运行时间最差为Ω(lgn)')
# python src/chapter6/chapter6_2.py
# python3 src/chapter6/chapter6_2.py
return self
if __name__ == '__main__':
print('Run main : single chapter six!')
Chapter6_2().note()
else:
pass