大家好，欢迎来到IT知识分享网。
目录
做Leecode题目: 滑动窗口最大值239时候碰到了有关最小堆的概念，这里记录学习以下。
1.满二叉树
k层，有
个结点，排列方式为从上到下，从左到右
3
2 3
4 5 6 7
2.完全二叉树
满二叉树是特殊的完全二叉树。笼统地说只要是从上到下，从左到右的排列方式都可以称为完全二叉树。
3
2 3
4 5 6
3.最小堆
最小堆是经过排序后的完全二叉树。二叉树的任意非终端节点的值不大于它的左子节点和右子节点的值。
Python中创建最小堆
q = list() heapq.heapify(q)2
3 3
4 5 6 7
4.最小堆的插入
从list插入2
list = [3,2,3,4,5,6,7] heapq.heappush(list,2)list作为一个二叉树(此时并非最小堆)
3
2 3
4 5 6 7
遵循从上到下，从左至右原则，2先会作为4的左子节点插入
3
2 3
4 5 6 7
2
即将2放在了列表list的最后
然而新数据2的父结点到根结点必然是一个有序的数列[4,2,3]
2会与父节点4比较，若小于4则会与4对调，对调后，会再与父节点2比较，若不大于2，则不会发生对调，所以最后的结果为
[3,2,3,2,5,6,7,4]
3
2 3
2 5 6 7
4
5.堆的删除
最小堆的删除是从下标为0的元素开始删除，然后将末尾的元素移动至第一位，然后再进行”下沉”，直到满足任意非终端节点的值不大于它的左子节点和右子节点的值。例，删除如上二叉树。
删除下标为0的元素
2 3
2 5 6 7
4
将末位元素移至顶点
4
2 3
2 5 6 7
下沉，按照顺序先与左子节点比较
2
4 3
2 5 6 7
继续下沉
2
2 3
4 5 6 7
6.关于堆
在堆中搜索并不是第一优先级，堆是为了实现排序而实现的一种数据结构，它不是面向查找操作的，因为在堆中查找一个节点需要进行遍历，其平均时间复杂度是O(n)。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/131426.html
