数据结构之堆
参考链接：https://blog.csdn.net/qq_44222205/article/details/107698844 https://zhuanlan.zhihu.com/p/265434444
堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为 O(1)。另外，因为取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为n，根据堆的形状特点可知树的高度为 log2n ，那么重构树的时间复杂度便为 O(logn)。添加数据也一样。在堆的最后添加数据后，数据会一边比较它与父结点数据的大小，一边往上移动，直到满足堆的条件为止，所以添加数据需要的运行时间与树的高度成正比，也是 O(logn)。堆通常是一个可以被看做一棵树的数组对象。
- 左侧子节点的位置是 2*index + 1
- 右侧子节点的位置是 2*index + 2
- 父节点位置是 (index-1)/2
堆的性质:
(1)结点内的数字就是存储的数据。堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。另外，结点的排列顺序为从上到下，同一行里则为从左到右。
(2)在堆中存储数据时必须遵守这样一条规则 ：子结点必定大于父结点。因此，最小值被存储在顶端的根结点中。往堆中添加数据时，为了遵守这条规则，一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端。
(3)堆中某个节点的值总是不大于或不小于其父节点的值；
(4)堆总是一棵完全二叉树。
(5)大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
(6）小顶堆：每个节点的值都小于或者等于它的左右子节点的值。
(4)堆总是一棵完全二叉树。
(5)大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
(6）小顶堆：每个节点的值都小于或者等于它的左右子节点的值。
投递牛客等公司8个岗位 >
查看14道真题和解析