Tag: 堆

堆数据结构实现— Swift 4

动机 这篇文章旨在帮助您了解堆数据结构并在Swift中实现它。 在进入实现部分之前，必须先具备swift和heap知识。 什么是堆 堆是一种完整的二叉树的特殊类型，它的父节点与其子节点进行比较，从而为您提供数据结构中的最大值或最小值。 通常有两种类型。 最大堆：在最大堆中，父节点将始终大于其子节点。 所有其他节点可以按任何顺序排列 最小堆：在最小堆中，父节点将始终小于其子节点。 所有其他节点可以按任何顺序排列 。 注意： 当您只关心最小值或最大值时，堆数据结构很有用。 所有其他值将是无序且无排序的。 优先级队列是可以使用堆数据结构的典型示例。 实作 现在，我们将实现具有所有功能的最小堆。 实现需要执行以下步骤： 1.向堆添加值 2.从堆中删除最少的元素 3.从堆中获取最少的元素 我们开工吧。 创建堆类 堆可以用数组表示。 一个父节点可以有一个左子节点和一个右子节点。 我们可以通过以下方式获取正确的Child的索引和离开的孩子的索引 左儿童索引= 2 *父索引+1 右子索引= 2 *父索引+2 用同样的方式 ParentIndex =（childIndex-1）/ 2 在堆类中实现所需的方法 将这些方法添加到堆类中。 现在，我们将添加在Heap上执行自定义操作的方法。 添加这些方法 peek（）返回堆中的最小元素 poll（）与peek一样，但是它也删除了最小元素 add（）将元素添加到堆中 removeMin（）删除堆中的最小元素 现在您一定在想，什么是heapifyDown（）和heapifyUp（） 让我们实现它们 堆砌 这是在将元素添加到列表之后发生的过程。 因此，如果要在堆中添加元素，只需将其添加到最后一个元素，然后开始与父元素进行比较，直到堆满足条件为止 HeapifyDown 当您删除列表中的最小元素并且堆必须重新排列自身以满足条件时，就会发生此过程。 对于父节点，它将检查子节点是否小于父节点（如果是），然后交换该值。 它一直持续到堆满足其先决条件为止。 让我们添加printMethod来打印堆 让我们使用这些方法来处理堆。 […]