农产品网站建设结构,h5长图用什么软件做,牛牛网站建设,潍坊住房公积金个人账户查询1.什么是堆
堆是一种满足以下条件的树#xff1a;
堆中的每一个节点值都大于等于#xff08;或小于等于#xff09;子树中所有节点的值。或者说#xff0c;任意一个节点的值都大于等于#xff08;或小于等于#xff09;所有子节点的值。 2.堆的用途
当我们只关心所有数…1.什么是堆
堆是一种满足以下条件的树
堆中的每一个节点值都大于等于或小于等于子树中所有节点的值。或者说任意一个节点的值都大于等于或小于等于所有子节点的值。 2.堆的用途
当我们只关心所有数据中的最大值或者最小值存在多次获取最大值或者最小值多次插入或删除数据时就可以使用堆。
有小伙伴可能会想到用有序数组初始化一个有序数组时间复杂度是 O(nlog(n))查找最大值或者最小值时间复杂度都是 O(1)但是涉及到更新插入或删除数据时时间复杂度为 O(n)即使是使用复杂度为 O(log(n)) 的二分法找到要插入或者删除的数据在移动数据时也需要 O(n) 的时间复杂度。
「相对于有序数组而言堆的主要优势在于更新数据效率较高。」 堆的初始化时间复杂度为 O(nlog(n))堆可以做到O(1)时间复杂度取出最大值或者最小值O(log(n))时间复杂度插入或者删除数据具体操作在后续章节详细介绍。
3.堆的分类
堆分为 「最大堆」 和 「最小堆」。二者的区别在于节点的排序方式。 「最大堆」 堆中的每一个节点的值都大于等于子树中所有节点的值 「最小堆」 堆中的每一个节点的值都小于等于子树中所有节点的值
如下图所示图 1 是最大堆图 2 是最小堆 4.堆的存储
之前介绍树的时候说过由于完全二叉树的优秀性质利用数组存储二叉树即节省空间又方便索引若根结点的序号为 1那么对于树中任意节点 i其左子节点序号为 2*i右子节点序号为 2*i1。
为了方便存储和索引二叉堆可以用完全二叉树的形式进行存储。存储的方式如下图所示 5.堆的操作
堆的更新操作主要包括两种 : 「插入元素」 和 「删除堆顶元素」。操作过程需要着重掌握和理解。
5.1插入元素
「1.将要插入的元素放到最后」
「2.从底向上如果父结点比该元素小则该节点和父结点交换直到无法交换」 5.2删除堆顶元素
根据堆的性质可知最大堆的堆顶元素为所有元素中最大的最小堆的堆顶元素是所有元素中最小的。当我们需要多次查找最大元素或者最小元素的时候可以利用堆来实现。
删除堆顶元素后为了保持堆的性质需要对堆的结构进行调整我们将这个过程称之为「堆化」堆化的方法分为两种 一种是自底向上的堆化上述的插入元素所使用的就是自底向上的堆化元素从最底部向上移动。 另一种是自顶向下堆化元素由最顶部向下移动。
自底向上堆化
1.首先删除堆顶元素使得数组中下标为 1 的位置空出。
2.比较根结点的左子节点和右子节点也就是下标为 2,3 的数组元素将较大的元素填充到根结点(下标为 1)的位置。
3.一直循环比较空出位置的左右子节点并将较大者移至空位直到堆的最底部 这个时候已经完成了自底向上的堆化没有元素可以填补空缺了但是我们可以看到数组中出现了“气泡”这会导致存储空间的浪费。接下来我们试试自顶向下堆化。
自顶向下堆化
自顶向下的堆化用一个词形容就是“石沉大海”那么第一件事情就是把石头抬起来从海面扔下去。这个石头就是堆的最后一个元素
1.我们将最后一个元素移动到堆顶。
2.然后开始将这个石头沉入海底不停与左右子节点的值进行比较和较大的子节点交换位置直到无法交换位置。 堆的操作总结 「插入元素」 先将元素放至数组末尾再自底向上堆化将末尾元素上浮 「删除堆顶元素」 删除堆顶元素将末尾元素放至堆顶再自顶向下堆化将堆顶元素下沉。也可以自底向上堆化只是会产生“气泡”浪费存储空间。最好采用自顶向下堆化的方式。
6.堆排序
堆排序的过程分为两步 第一步是建堆将一个无序的数组建立为一个堆 第二步是排序将堆顶元素取出然后对剩下的元素进行堆化反复迭代直到所有元素被取出为止。
6.1建堆
建堆的过程就是一个对所有非叶节点的自顶向下堆化过程。
首先要了解哪些是非叶节点最后一个节点的父结点及它之前的元素都是非叶节点。也就是说如果节点个数为 n那么我们需要对 n/2 到 1 的节点进行自顶向下沉底堆化。
具体过程如下图 将初始的无序数组抽象为一棵树图中的节点个数为 6所以 4,5,6 节点为叶节点1,2,3 节点为非叶节点所以要对 1-3 号节点进行自顶向下沉底堆化注意顺序是从后往前堆化从 3 号节点开始一直到 1 号节点。堆化结果 6.2排序
由于堆顶元素是所有元素中最大的所以我们重复取出堆顶元素将这个最大的堆顶元素放至数组末尾并对剩下的元素进行堆化即可。
我们需要执行自顶向下沉底堆化这个堆化一开始要将末尾元素移动至堆顶这个时候末尾的位置就空出来了由于堆中元素已经减小这个位置不会再被使用所以我们可以将取出的元素放在末尾。
