数据结构与算法Python语言实现《Data Structures & Algorithms in Python》手写课后答案--第九章_数据结构与算法python语言实现pdf古德里奇

第九章

本章讲述优先级队列，对结构堆进行学习应用，较简单

习题代码如下(部分代码引用书中源代码，源代码位置目录在第二章答案中介绍)

# 堆结构可进行部分排序
# 9.1 logn个元祖,每删除一个根元节点将花费logn的时间，所以总时间为logn*logn=log(n^n)
# 9.2 令根节点为第0个访问的元素。设元素访问的index为d，满足第2*d+1 和2*d+2访问的元素大于第d个访问的元素即可
# 9.3 (5,A)、(4,B)、(4,B)、(1,D)、(4,B)、(3,J)、(3,J)、(4,B)、(5,A)、(5,A)、(6,L)、(2,H)、(6,L)、(7,F)
# 9.4 基于堆的优先级队列，可以在logn的时间内添加事件、并可以在logn的时间内取出最小的事件
# 9.5 分配空间储存最小值，在remove_min() 重新确定最小值, 在min()直接返回min
#Algorithm UnsortedPriorityQueue():
#   Algo __init__(self):
#       self._min=None          # creat a attribute to store the min item
#
#   Algo add(self,key,value):
#       token=self._Item(key,value)     # conpare the _min every add
#       if self._min==None or self.min>token:
#           self._min=token
#
#   Algo min(self):
#       return self._min
#
#   Algo remove_min(self):           # remove the min and get back the min 
#       item = self._data.delete(p)
#       self._min=self._find_min()  
#   return (item._key, item._value)

# 9.6 不可以，当删除最小值时，必须寻找下一个最小值来维护程序，
# 9.7 选择排序，将所有的序列放在a中，每次返回a中最小的元素进行排列
# 9.8 插入排序，在放有所有元素的序列a中，每次选取1个(有规则的)插入到空序列b中
# 9.9 {1,2,3,4(从小到大的顺序)} 
# 9.10 堆的第2层或者第1层  (根节点为0层)
# 9.11 堆的叶子结点
# 9.12 修改ADT中 向上冒泡和向下冒泡方法中 键值大小的比较
# 9.13 第一步从叶子结点的父节点开始，自下向上重构(面向最大值的)堆，
#      第二部然后将堆定和堆底交换位置并将边界前移
#      重复第二步知道堆中只有一个元素，返回数组
# 9.14 不是  堆需要满足两点要求：1是完全二叉树;2满足heap-oreder。他并没有会所position tree 满足要求2
# 9.15 完全二叉树的要求不允许一个节点有右孩子没有左孩子
# 9.16 先序和后序遍历可以存在。中序遍历不可以，在完全二叉树中，树的根节点在中序遍历的最中间处，此处节点不满足最小值
# 9.17
#先序  {0，1，3，7，8，4，9，10，2，5，11，12，6，13，14}
#中序  {7，3，8，1，9，4，10，0，11，5，12，2，13，6，14}
#后序  {7，8，3，9，10，4，1，11，12，5，13，14，6，2，0}
# 9.18
#实际时间A=sum(logi)   B=nlogn
# 当n=1时,A=B;当n>1时A<B;所以命题成立
# 9.19 让堆中非叶子结点的左孩子大于右孩子，非严格意义上的降序(先序遍历的部分为降序)
# 9.20 让堆中非叶子结点的左孩子小于右孩子，非严格意义上的生序(先序遍历的部分为升序)
# 9.21 在数组中,通过索引将(16,X)与(13,W)交换位置，删除(16,X)，然后将(13,W)向上冒泡，然后在向下冒泡，完成操作
# 9.22 在数组中,通过索引将(5,A)的键值更换为18,然后尝试向上冒泡，和向下冒泡
# 9.23                            1
#               3                                   33
#         5             7                  35                   37
#     9      11     13    15          39        41         43         45  
#  17  19  21  23 25  27 29  31     47   49   51   53    55   57    59
# 9.24 每插入一个节点,在做坏的情况下需要将节点从叶子结点移到根节点,时间需要logn;n个节点就最多需要nlogn
# 9.25                                         数组         堆
#重构面向最大值的堆                              975264      975264
#将堆的根节点和尾节点交换，并将堆的长度减少1         475269      47526      
#对根节点进行bubbling                           765249      72564
#然后重复,直到堆只有根节点                        245679      2
# 9.26 添加一个整形实例变量A，这个实例变量记录入栈的序号，堆按照(堆内元素总数-A进行构造)
# 9.27 添加一个整形实例变量A，这个实例变量记录入栈的序号,堆按照A的大小进行构造
# 9.28 不行，如果先存10个元素，最后一个元素A的值为10，然后outup9个元素，input2个元素(B,C)，这种情况A元素就不符合FIFO规则
# 9.29
from TheCode.ch09.priority_queue_base import PriorityQueueBase
class SortedPriorityQueue1(PriorityQueueBase):
    ''' base of array ADT'''
    def __init__(self):
        self._data=[]

    def __len__(self):
        return len(self._data)

    def add(self,k,value):
        ''' append a item to the data,and sort it'''
        self._data.append(self._Item(k,value))
        walk=self._data[-1]
        for i in range(len(self._data)-1,-1,-1):    # bubbling sort 
            if self._data[i]>walk:
                walk,self._data[i]=self._data[i],walk
                walk=self._data[i]
    def min(self):
        return self._data[0]._key,self._data[0]._value

    def remove_min(self):
        temp=self._data.pop(0)
        return temp._key,temp._value
#t=SortedPriorityQueue1()
#for i in range(10,0,-1):
#    t.add(i,str(i))
#print(t.remove_min())
# 9.30
from TheCode.ch09.heap_priority_queue import HeapPriorityQueue
class HeapPriorityQueue1(HeapPriorityQueue):

    def _upheap(self,j):
        '''j and i both are index '''
        parent = self._parent(j)
        while (j > 0 and self._data[j] < self._data[parent]):
            self._swap(j, parent)
            j=parent
            parent=self._parent(j)
# 9.31            
    def _downheap(self,j):
        
        walk=self._left(j) if (self._data[self._left(j)]<self._data[self._right(j)]
                               or not self._has_right()) else self._right(j) # find the min node
        while(j<len(self) and self._data[j]>self._data[walk]):
            self._swap(j,walk)
            walk=self._left(j) if (self._data[self._left(j)]<self._data[self._right(j)]
                               or not self._has_right()) else self._right(j) # find the min node
            
    def heappushpop(self,key,value):
        ''' push and pop'''
        self._data[0]=self._Item(key,value)   # chang the root node
        self._downheap(0)              # bubbling the node
        return self.min()

    def heapreplace(self,key,value):
        ''' pop and push'''        
        self.min()
        self._data[0]=self._Item(key,value)   # chang the root node
        self._downheap(0)              # bubbling the node
        return self.min()
        
heap=HeapPriorityQueue1() 

#for i in range(10,0,-1):
#    heap.add(i,chr(i*10))
#text 9.30-31
#print(heap.min())
#text 9.39
#print(heap.heappushpop(-1,')'))
#print(heap.min())
# 9.31 在9.30类中的_downheap方法
# 9.32
#第一步：计算出树的深度h(从0开始)，和最后一层元素的个数l
#第二步：计算最后一层最大元素数k=2^h，将其平均分成两部分a，b
#第三部：从根节点开始出发，如果l在a的范围中，进入当前节点的左子树，否则右子树
#第四部：将进入的范围继续分为两部分，重复步骤二，直到当前节点为叶子节点

# 9.33 创建一个列表l，将叶子结点从左到右保存，修改_switch(a,b)方法,
#  每次使用后如果a是叶子节点，则将l中的节点和b交换
#  remove方法需要将 最后节点移除,add方法需要将检查添加节点处的父节点是不是叶子节点进行一系列操作

# 9.34
# 先进入最左节点，例如得出'0000'记为a，'1111'记为b，如果b存在，则输出'1111'
# 否则 c记为 (int(a)+int(b))/2; c存在a=c，不存在b=c，重复第上一步直到a+1=b
# 输出a

# 9.35
#Algorithm text35(root,k):
#   if root._key>k or root==None:
#       return
#   yield root._key,root._value
#   for i in text35(root._right):
#       yield i
#   for i in text35(root._left):
#       yield i

# 9.36
# len min 等操作 时间为O(1)
# add remove  remove_min      O(logn)*   修改动态数组涉及均摊算法，因为只修改一个元素所以均摊为logn+1=O(logn)*
# update  使用bobbling函数

# 9.37 题目意思似乎是使用计算的方法求得堆的构造时间复杂度为O(n)
#  time= sum(2^(h-i)*i)   {h为树的高度，从0开始;i从1开始趋近于h}
#      = 2^(h+1)-2-h
#      = 2n-2-logn

# 9.38 如果在基于数组的heap中，时间复杂度有两种情况O(m+n)和O(mlogn)
#      在基于链表的heap中，只需要移除某棵树的叶子节点作为根节点，然后连接两个树的根节点，_downheap()

# 9.39在9.30类中的heappushpop方法

# 9.40在9.30类中的heapreplace方法

# 9.41 原排序算法时间复杂度为O(nlogn),使用堆结构，重构堆然(O(n))后从堆的根节点开始remove_min(O(2logn))
#       总O(n)

# 9.42 使用O(n)的时间复杂度构造 maximum_oriented heap的堆，然后每次remove需要O(logn),排出k个就需要O(k*logn)
#       总(n+k*logn)

# 9.43 使用O(k)个空间构造面向最大值的堆结构,遍历拥有n个元素的无序列表尝试将元素填入堆中;最后将堆中的元素remove 出

# 9.44 提供了面向最小值的PriorityQueue类，让完成面向最大值的优先级队列,PriorityQueue使用HeapPriorityQueue类
# 将键值*-1存入，返回时*-1
from TheCode.ch09.heap_priority_queue import HeapPriorityQueue
class MaxPriorityQueue(HeapPriorityQueue):
    
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187