卓伊科技网站建设,安徽宿州住房与城乡建设玩网站,神木网站设计公司,京东网上购物1.简介 堆是一种特殊的数据结构#xff0c;通常用于实现优先队列。堆是一个可以被看作近似完全二叉树的结构#xff0c;并且具有一些特殊的性质#xff0c;根据这些性质#xff0c;堆被分为最大堆#xff08;或者大根堆#xff0c;大顶堆#xff09;和最小堆两种。
2.…1.简介 堆是一种特殊的数据结构通常用于实现优先队列。堆是一个可以被看作近似完全二叉树的结构并且具有一些特殊的性质根据这些性质堆被分为最大堆或者大根堆大顶堆和最小堆两种。
2.基本性质 完全二叉树结构堆必须是一棵完全二叉树即除了最底层其他层都是满的而且最底层的节点都尽量靠左排列最后一行元素之间不可以有间隔。堆序性质 堆分为最大堆和最小堆两种。在最大堆中任意节点的值都大于或等于其子节点的值在最小堆中任意节点的值都小于或等于其子节点的值。
3.节点下标间的规律 因为堆是一棵完全二叉树若父节点的下标为i则左子节点下标为2i1,右子节点下标为2i2,这个规律会在算法排序中经常使用。
4.堆的基本操作 上滤Percolate Up
上滤是指在堆中插入新元素后通过一系列的比较和交换操作将该元素上移到合适的位置以保持堆的堆序性。通常用于最小堆和最大堆中。
步骤
将新元素插入到堆的末尾底部。比较该元素与其父节点的值。如果该元素的值比父节点的值更小对于最小堆或更大对于最大堆则交换它们。重复步骤2和步骤3直到满足堆的性质为止。
下滤Percolate Down
下滤是指在删除堆顶元素后通过一系列的比较和交换操作将堆的最后一个元素通常是堆底元素移到堆顶并将其下移到合适的位置以保持堆的堆序性。
步骤
将堆的最后一个元素通常是堆底元素移到堆顶。比较该元素与其子节点中较小对于最小堆或较大对于最大堆的一个。如果该元素的值比子节点的值更小对于最小堆或更大对于最大堆则交换它们。重复步骤2和步骤3直到满足堆的性质为止。
应用场景
上滤 通常在插入新元素时使用确保新元素的插入不破坏堆的性质。下滤 通常在删除堆顶元素后使用以恢复堆的性质。
堆化Heapify
堆化Heapify是指将一个无序的序列转换成一个堆可以是最小堆或最大堆。堆化过程可以分为两种自底向上堆化Bottom-Up Heapify和自顶向下堆化Top-Down Heapify。
自底向上堆化Bottom-Up Heapify
自底向上堆化是从序列的最后一个非叶子节点开始逐步向前处理每个节点使得以该节点为根的子树成为一个堆。该方法保证了子树堆化后整个序列也是一个堆。
步骤 从序列的最后一个非叶子节点开始通常是 n/2-1其中 n 是序列的长度。 对每个非叶子节点与其子节点比较如果不满足堆的性质则进行交换。 重复上述步骤直到处理完整个序列。
自顶向下堆化Top-Down Heapify
自顶向下堆化是从序列的第一个元素开始逐步向后处理每个节点使得以该节点为根的子树成为一个堆。该方法保证了每个节点都满足堆的性质。
步骤 从序列的第一个元素开始。 对每个节点与其子节点比较如果不满足堆的性质则进行交换。 重复上述步骤直到处理完整个序列。
应用场景
建堆 堆化是建立堆的关键步骤可以在 O(n) 的时间复杂度内将一个无序序列转化为堆。堆排序 在堆排序算法中首先对待排序序列进行堆化然后反复取出堆顶元素直到堆为空实现排序。优先队列 堆被广泛应用于实现优先队列堆化操作确保队列中优先级最高的元素位于队首。
推荐观看 【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆
