iOS 数据结构之堆

作者: 人魔七七 | 来源:发表于2018-06-04 16:38 被阅读166次

iOS 数据结构之链表
iOS 数据结构之堆
iOS标准库中常用数据结构和算法之排序
数据结构之「堆」
数据结构之堆
数据结构和算法
iOSer必须了解的数据结构
数据结构与算法之美-28讲堆和堆排序
(八)数据结构之堆
堆结构的实现

堆

一个堆是一个二叉树，是以数组的方式存在，因此他不用父子指针。这个树由于堆的特性是部分有序的，这个特性决定着这些节点在树中的顺序。

一些堆的常用用法

1：用来构建一些优先级队列
2：堆是一个支持堆排序的数据结构
3：当你需要计算一个集合中最大或者最小的元素的时候堆是你的选择

堆有什么特性呢

有两种类型的堆，一个是类似最大元素是父节点下面是子节点，一个是相反的最小的元素是父节点下面的比较大的元素。思路大致相同，除了他们在存储节点的顺序。
由于堆的这个特性，通常max-heap 存储最大的元素在根节点，min-heap相反的是最小的元素在根节点。这样是非常有用的，这种数据结构通常被用来构建优先级队列。这种队列通常能快速的找到我们要的元素比如最大的或者最小的。
注意的是max-heap 最大的元素总是索引是0但是最小的元素不一定是最后一个，唯一保证的是他是一个叶子节点而已。

堆和标准的树有什么相同点和不同点

1：堆不是为了替代二叉搜索树，但是他们之间是有一些异同点，下面是一些最大的区别：
2：节点的顺序：在搜索二叉树中，左边的叶子节点必须一直比根节点小并且右边的叶子节点必须比根节点大。对堆而言并不是这样。在max-heap中左右子节点一定比根节点小，反之 min-heap中左右子节点一定比根节点大。
3：内存的使用：传统的树需要使用更多的内存不只是存储数据。你需要分配额外的存储给节点对象以及指向他们的指针。堆仅仅使用一个简单的数组，不使用指针。
4：平衡性：一个搜索二叉树必须是平衡的所以很多操作是O（log n）的复杂度。你可以插入删除节点数据用一些AVL Tree red-black tree。但是对于堆来说我们不需要整个树是有序的。堆的一些操作的复杂度是O（log n）
5：搜索：搜索二叉树是很快的这本来就是他实现的一个目的。在堆中搜索是慢的，他的目的总是把最大或者最小的节点放在前面，允许快速的插入或者删除操作，搜索并不是他要实现的目的。

用数组的方式实现树

用数组的方式实现树的结构看起来很奇怪，但是在时间和空间复杂度上更高效。

[ 10, 7, 2, 5, 1 ]
但是我们怎么知道哪些是根节点哪些是子节点，如果我们不用指针。这些节点之前的关系和他们在数组的关系是密切相关的。
如果i 是这个节点的索引。然后有下面这个公式。
parent(i) = floor((i - 1)/2)
left(i) = 2i + 1
right(i) = 2i + 2

一些数学公式

1：一个堆如果深度是h 那么他的层级是h+1层 h 是3那么是3+1 个层级
2：那么一个堆的深度和节点数的关系是 h = floor(log_2(n)). floor(log_2(15)) = floor(3.91) = 3
3：每层深度的节点个数2^h 剩下上面的节点个数是2^h - 1
4：这个树所有的节点个数是2^(h+1) - 1
5：最下层的叶子节点在数组中的索引是floor(n/2) to n-1

一些堆的操作

当你插入或者删除某个元素到堆中的时候，你需要确保这个堆是有效的 valid max-heap 或者 min-heap
shiftUp ：如果这个元素比父节点大（ max-heap）或者比父节点小（min-heap）。那么你要保证这个堆的有效性你要把这个元素和父节点交换。这就使这个元素向上调整的过程
shiftDown：如果这个元素比子节点小（ max-heap）或者比子节点大（min-heap）那么需要heapify，就是想下调整这个元素的过程。
这两个操作是一个递归的操作花费O(log n) 时间复杂度。
其他的一些操作都是建立在这两个操作上面的。
1：在堆中插入一个元素。在堆的尾部添加元素并且用shiftUp来修复使符合对的特性。
2：删除元素的操作。删除并且返回max-heap的最大元素或者删除并范围max-heap的最小元素。填充因为删除元素留下的空隙，最近的元素被移动到删除元素的位置通过shiftDown操作来使剩下的元素符合堆的特性。
3：删除某个索引下的元素：和删除根节点不同需要，这需要所有元素shiftDown，有可能删除的是子节点或者有可能删除的是父节点
4：交换元素:当插入或者删除元素时候，造成现在的结构可能不是堆，所以要进行一些元素的交换使现在的结构是堆。
所有上面的这些操作时间复杂度O(log n)
推导一下公式：
不管是Insert还是Delete，都是上下层之间的比较，所以最多的“比较后互换”操作的次数就是总层数。
对于一个L层的二叉树，树的长度 n = 2^0 + 2^1 + 2^2 + ... + 2^(L-1)
根据等比数列求和公式，n = 2^L - 1
所以，L = log2(n + 1)
所以最坏情况就是就是log2(n + 1)次操作，即O(log n)。
还有一些操作花费更多的时间比如：
5：搜索某个元素：堆这个结构不是为了高效的搜索存在的，如果替换或者删除元素需要知道这个节点在数组中的索引，因此有些时候你需要找到这个元素的索引时间的复杂度是O（n）
从数组中构建堆：把一个没有排序的数组变成一个数组需要不断的插入元素的操作。这是个O（n）的操作。
6：堆排序：由于堆其实是一个数组，我们可以用这个独特的特性给数组排序。这个时间复杂度是O(n lg n).
7：还有一个peek函数返回堆中最大或者最小的元素，并不要从堆中删除他。时间复杂度是O（1）

插入一个元素到堆中

举个例子

在数组中就是[ 10, 7, 2, 5, 1 ]。
第一步我们插入一个元素就是在数组的最后添加一个元素，现在数组变成：[ 10, 7, 2, 5, 1, 16 ]
现在树变成这样：

这个16对于这个max-heap来说位置不合适，因为他比父节点大。所以我们把16和2交换。

现在结束了吗？很显然16比10大，所以和10交换

现在所有的父节点比子节点大。
把元素上移这个操作和这个树的深度有关系因此需要O(log n)的时间复杂度。把节点添加到数组的末尾的时间复杂度是O（1），所以可以忽略不计。

删除堆的根节点

我们删除10这个元素从这个树中。

现在顶部如果为空应该怎么办？

让我们回想一下之前的插入操作，我们把最新的数组放在了数组的最后面。这里我们正好相反，我们把这个数的最后一个元素放到树的顶端，然后做一些操作把这个结构变为堆就行了。

让我们比较下1和他的左右子节点，由于这是个max-heap，我们把7和2中最大的和1交换变成了下图

然后继续交换直到符合max-heap的特性

这个操作的时间复杂度和这个树的深度有关系，所以他的时间复杂度是O(log n)。

删除堆的任何一个元素

我们删除7这个元素
[ 10, 7, 2, 5, 1 ]
删除元素后为了保持堆的特性我们需要把他和最后一个元素交换。变成这样
[ 10, 1, 2, 5, 7 ]
1比子节点5小，所以交换下。

把数组变成堆的过程

我们循环把所有的元素插入堆中，这个不是太高效，需要花费O(n log n)时间复杂度一共因为一共n个元素每个元素插入需要O(log n)的时间复杂度。

在堆中搜索

由于这个堆的设计不是为了最快搜索。但是我们如果删除等操作的时候，我们需要获取这个元素的索引。因此搜索是用来做这个的虽然慢。
在搜索二叉树中你可以依赖这些节点的顺序来快速搜索。但是堆并不适用。

如果我们要搜索1 那么按照[ 10, 7, 2, 5, 1 ] 的数组顺序来线性搜索。我们知道max-heap中父节点总比子节点大，所以我们可以忽略子节点以及子节点的子节点，如果这个父节点比我们找到元素小。
举个例子我们找一个元素8这个不存在堆中。我们从根节点10开始，由于10明显不是我们递归的查看他的左右子节点。左边的子节点是7，这也不是我们找的元素，但是由于这个是max-heap，我们知道7的子节点更没有必要查找，因为他们都是小于7也就是不等于8，同样这个2也是。
尽管有这个小小的优化，搜索的时间复杂度仍然是O（n）。
注意:可以通过把节点值和索引映射到字典中。