江苏网站建设哪家有,免费推广网站有哪些有哪些,江门网站制作培训,wordpress支付宝个人目录简介堆是一个二叉树#xff0c;它的每个父节点的值都只会小于或大于所有孩子节点(的值)。它使用了数组来实现#xff1a;从零开始计数#xff0c;对于所有的 k #xff0c;都有 heap[k] heap[2*k1] 和 heap[k] heap[2*k2]。 为了便于比较#xff0c;不存在的…目录简介堆是一个二叉树它的每个父节点的值都只会小于或大于所有孩子节点(的值)。它使用了数组来实现从零开始计数对于所有的 k 都有 heap[k] heap[2*k1] 和 heap[k] heap[2*k2]。 为了便于比较不存在的元素被认为是无限大。 堆最有趣的特性在于最小的元素总是在根结点heap[0]。类似于C的优先队列。heapq创建heapq.heapify(x)将list x 转换成堆原地线性时间内。 from heapq import * heap [2,7,4,1,8,1] heapify(heap) print(type(heap),heap) [1, 1, 2, 7, 8, 4]添加heappush(heap, item)将 item 的值加入 heap 中保持堆的不变性。 heappush(heap,9) print(heap)[1, 1, 2, 7, 8, 4, 9]删除heappop(heap)弹出并返回 heap 的最小的元素保持堆的不变性。如果堆为空抛出IndexError。使用 heap[0] 可以只访问最小的元素而不弹出它。 heappop(heap)1 print(heap)[1, 7, 2, 9, 8, 4]高效增删heappushpop(heap, item)将 item 放入堆中然后弹出并返回 heap 的最小元素。该组合操作比先调用heappush()再调用heappop()运行起来更有效率。 heappushpop(heap,9)1 print(heap)[2, 7, 4, 9, 8, 9]heapreplace(heap, item)弹出并返回 heap 中最小的一项同时推入新的 item。 堆的大小不变。 如果堆为空则引发IndexError。这个单步骤操作比heappop()加heappush()更高效并且在使用固定大小的堆时更为适宜。 pop/push 组合总是会从堆中返回一个元素并将其替换为 item。返回的值可能会比添加的 item 更大。 如果不希望如此可考虑改用heappushpop()。 它的 push/pop 组合会返回两个值中较小的一个将较大的值留在堆中。堆的实现堆的特点内部数据是有序的可以弹出堆顶的元素大根堆就是弹出最大值小根堆就是弹出最小值每次加入新元素或者弹出堆顶元素后调整堆使之重新有序时间复杂度O(logn)堆的本质它是一个完全二叉树实现的时候不需要建造一个树改用一个数组即可一直一个节点的索引为index那么父节点的索引为左孩子节点编号为index*21右孩子节点为index*22树以序列2,7,4,1,8,1为例最后形成的二叉树如上图所示列表见下表堆对应的实际列表元素874121下标012345添加元素放入列表尾列表尾元素向上调整和父节点交换直到当前元素不符合交换条件(大根堆时就是大于父节点需要调整小根堆反之)插入8的过程以插入8为例8插入到列表末尾列表为7 2 4 1 8之后8与2比较后交换改为7 8 4 1 2之后8与7比较后交换改为8 7 4 1 2结束。删除交换堆顶元素与末尾元素删除列表末尾元素新的堆顶元素向下调整和子节点交换直到当前元素不符合条件(大根堆时就是小于子节点(选择更大的子节点)需要调整小根堆反之)初始化def __init__(self, descTrue):init a heap, default big root heap:param desc:True,big root heap;False, little root heap.self.heap []self.desc desc初始化一个大根堆参数desc:降序默认为True大小propertydef size(self)::return: size of heapreturn len(self.heap)返回堆的大小即列表长度得到堆顶def top(self):get top of heap:return: the top of heaptry:return self.heap[0]except Exception:raise IndexError(heap is empty.)返回堆顶元素如果堆为空引发IndexError。添加def push(self, val):add an element to heap:param val: the value of element:return: Noneself.heap.append(val)self._to_up(self.size - 1)return None把元素添加到尾部再向上调整参数val待添加元素的值_to_up向上调整def _to_up(self, index):adjust bottom one to up:param index:size of heap - 1:return: Nonewhile index:parent (index - 1) // 2if self._better(self.heap[parent], self.heap[index]):breakself.heap[parent], self.heap[index] self.heap[index], self.heap[parent]index parentreturn None尾部元素调整到上面参数index:长度-1def _better(self, node1, node2):return node1 node2 if self.desc else node1 node2选择一个符合条件的根据desc来判断删除def pop(self):delete the top of heap:return:the top of heapitem self.heap[0]self.heap[0], self.heap[-1] self.heap[-1], self.heap[0]self.heap.pop()self._to_down(0)return item删除堆顶元素返回堆顶元素def _to_down(self, index):adjust top one to down:param index: 0:return: Nonewhile index * 2 1 self.size:best indexleft index * 2 1right index * 2 2if self._better(self.heap[left], self.heap[best]):best leftif right self.size and self._better(self.heap[right], self.heap[best]):best rightif best index:breakself.heap[index], self.heap[best] self.heap[best], self.heap[index]index bestreturn None以大根堆为例判断是否存在左孩子若存在找出当前节点和左孩子中更大的判断是否存在右孩子若存在找出当前节点和右孩子中更大的若当前节点是最大的不变否则交换当前节点和最大的参数index:0结果截图全部代码--coding:utf-8--File: heap.py.pyAuthor:frank yuDateTime: 2020.12.31 11:15Contact: [email protected]Description:class Heap:def __init__(self, descTrue):init a heap, default big root heap:param desc:True,big root heap;False, little root heap.self.heap []self.desc descpropertydef size(self)::return: size of heapreturn len(self.heap)def top(self):get top of heap:return: the top of heaptry:return self.heap[0]except Exception:raise IndexError(heap is empty.)def push(self, val):add an element to heap:param val: the value of element:return: Noneself.heap.append(val)self._to_up(self.size - 1)return Nonedef pop(self):delete the top of heap:return:the top of heapitem self.heap[0]self.heap[0], self.heap[-1] self.heap[-1], self.heap[0]self.heap.pop()self._to_down(0)return itemdef _better(self, node1, node2):return node1 node2 if self.desc else node1 node2def _to_up(self, index):adjust bottom one to up:param index:size of heap - 1:return: Nonewhile index:parent (index - 1) // 2if self._better(self.heap[parent], self.heap[index]):breakself.heap[parent], self.heap[index] self.heap[index], self.heap[parent]index parentreturn Nonedef _to_down(self, index):adjust top one to down:param index: 0:return: Nonewhile index * 2 1 self.size:best indexleft index * 2 1right index * 2 2if self._better(self.heap[left], self.heap[best]):best leftif right self.size and self._better(self.heap[right], self.heap[best]):best rightif best index:breakself.heap[index], self.heap[best] self.heap[best], self.heap[index]index bestreturn Nonedef create(self, seq):for val in seq:self.push(val)return Nonedef menu():print(--------------------Menu--------------------)print(1.Create 2.Push)print(3.Pop 4.Top)print(5.Size)print(e.Exit)if __name__ __main__:seq input(please enter a sequence separated by white space:)# use seq to create a big root heapheap Heap()heap.create(seq.split())while True:menu()choice input(please select an option)if choice e:breakif choice 1:seq input(please enter a sequence separated by white space:)heap.create(seq.split())elif choice 2:val input(please enter a value:)heap.push(val)print(f{val} has insert into heap.)elif choice 3:val heap.pop()print(f{val} has been deleted.)elif choice 4:val heap.top()print(fthe top of heap is {val}.)elif choice 5:size heap.sizeprint(fthe size of heap is {size}.)else:print(something wrong, check your input.)有问题请下方评论转载请注明出处并附有原文链接谢谢如有侵权请及时联系。如果您感觉有所收获自愿打赏可选择支付宝18833895206(小于)您的支持是我不断更新的动力。
