国外代码开源网站,伴奏网站防盗是怎么做的,基于windows搭建wordpress,seo网络科技有限公司堆的简单实现与代码实现
堆的定义
在定义堆#xff08;heap#xff09;之前#xff0c;先回顾一下完全二叉树的定义#xff1a;
完全二叉树#xff1a;除了最后一层的结点有可能没有达到最大值外#xff0c;其它层的结点值都达到最大值#xff0c;此外最后一层的叶子…堆的简单实现与代码实现
堆的定义
在定义堆heap之前先回顾一下完全二叉树的定义
完全二叉树除了最后一层的结点有可能没有达到最大值外其它层的结点值都达到最大值此外最后一层的叶子结点会尽可能连续集中在左边 堆的基本定义堆是一种是基于树的专用数据结构一般是将一颗完全二叉树的结点按照层序遍历的顺序存于数组中来实现的
堆具有以下几个特性
在堆中最高(或最低)优先级的元素始终都存储在堆的根目录(第一个储存元素的位置)堆中的父结点优先级总是大于等于(或小于等于)其子结点但是其子结点并没有大小顺序之分因此堆不能称作一种顺序数据结构但是可以被当做是一种部分排序的储存结构堆的层次之间存在一个特殊关系利用这个关系可以代替索引的功能找到对应的元素
堆的层次关系
如果一个结点的位置为k ,则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k1。这样,在不使用指针的情况下.也可以通过计算数组的索引|在树中上下移动:从a[k]向上一层,就令k等于k/2,向下一层就令k等于2k或2k1。 这里0索引不使用因为索引从1开始会让操作更方便
堆中插入元素append()使用的排序方法之一上浮swim()过程 堆中删除最大元素的排序方法之一下沉sink()过程 下面用代码实现堆层次往下时元素的值从大到小排列
堆的操作方法
less()比较插入堆中的结点与当前节点的大小辅助排序swap()交换结点的值一般与less合用达到排序效果append()向堆中尾部插入一个元素其内部的swim()利用了堆的层次关系对元素进行上浮操作实现父子结点间的大小排序delete_max()删除最大元素并返回其最大值其内部的sink()利用了堆的层次关系对元素进行下沉操作实现父子结点间的大小排序
堆的Python代码实现
import operatorclass Heap:def __init__(self):self.items [None]self.N 0 # The size of this heapdef less(self, i, j):return operator.lt(self.items[i], self.items[j])def swap(self, i, j):self.items[i], self.items[j] self.items[j], self.items[i]def append(self, item):Append an element to its tail and do not use the index 0self.items.append(item)self.N 1def swim(k):Adjust the elements position, keeping the heap sequentialwhile k 1:if self.less(int(k / 2), k):self.swap(int(k / 2), k)k int(k / 2)swim(self.N)def delete_max(self):Delete the max value(the item where index1) in this heap and return itif self.N 1:return# Swap items[1] with items[-1]_max self.items[1]self.swap(1, self.N)# Delete items[-1]del self.items[self.N]# The length of this heap subtract 1self.N - 1# print(fLength: {self.N}, Length-real: {len(self.items)-1})# Sink() to adjust the sequence of this heapdef sink(k):Compare the current element with the max of its child nodeswhile 2 * k self.N:# Take the max childs indexindex_of_max_child 2 * k if 2 * k 1 self.N else \(2 * k 1 if self.less(2 * k, 2 * k 1) else 2 * k)# When we found the position in where it should be, break the loopif self.less(index_of_max_child, k):break# Else, swap the current nodes value with its max child nodes valueself.swap(k, index_of_max_child)# Swap the current index with index_of_max_child, continue to do the while loopk index_of_max_childsink(1)# Return the max valuereturn _max代码测试
if __name__ __main__:heap Heap()heap.append(A)heap.append(B)heap.append(C)heap.append(D)heap.append(E)heap.append(F)heap.append(G)print(heap.N)# Iteratively delete the element in this heapres heap.delete_max()while res:print(res, end )res heap.delete_max()
测试结果
7
G F E D C B A 是从小到大插入的元素但是是依次取出最大元素所以结果是从大到小排列注意根据插入顺序的不同可能中间会有元素不是按照大小顺序排放但是整体是从大到小排列的
