UE4的TArray（三）

TArray除了最基本的数组容器功能外，相比于std::vector来说，最不一样也是最有特色的地方，就是还能当作二叉堆来使用。提供的几个函数可以轻而易举的让TArray变成小根堆，大根堆，然后还可以做堆排序，堆插入，堆删除。可能你会说快速排序和堆排序复杂度相同，直接快速排序就好了，干嘛费这么大功夫用维护一个堆。但在实际业务中，有不少情况用堆来实现功能会有明显的优势。最后会具体来说，先来介绍基本用法。

先来做一些准备工作：

学过数据结构都知道，用数组来实现堆，左子节点的索引是Index * 2 + 1 ，右子节点是Index * 2 + 2，父节点是(Index - 1) / 2，判断是否为叶子节点，只要判断左子节点是否大于等于数组数量就可以了。UE4已经封装好了这3个基本操作，如上面代码所示。

可以举个例子来直观的说明一下，现在有一个数组：

我按照上面规则，我简单写了一个代码，按照堆的形式可视化打印到log里，方便后面理解：

上面TArray数组按照堆的规则打印的结果

可以看到，23是堆顶，456和1232是堆顶的左右子节点，依次向下递归就是整个堆

打印代码如下（这段用文本贴的，方便大家ctrl+c，没IDE变色，关键字看着不明显）

void MakeHeapPrefix(TArray<FString>& Output, int32 Index = 0)
{
	static FString ChildPrefix[] = {TEXT("│ "), TEXT("  ")};
	static FString SelfPrefix[] = {TEXT("└─"), TEXT("┌─")};
	static FString Spaces = TEXT("  ");
	const int32 LeftChildIndex = Index * 2 + 1;
	const int32 RightChildIndex = LeftChildIndex + 1;
	const int32 Parent = (Index - 1) / 2;
	// 自己和父节点是左右/右左的情况有竖线，左左/右右是空白
	if (Parent > 0)
	{
		Output[Index] = Output[Parent] + Spaces + ChildPrefix[(Index + Parent + 1) % 2];
	}
	if (LeftChildIndex < Output.Num())
	{
		MakeHeapPrefix(Output, LeftChildIndex);
	}
	if (RightChildIndex < Output.Num())
	{
		MakeHeapPrefix(Output, RightChildIndex);
	}
	if (Index > 0)
	{
		Output[Index] = Output[Index] + Spaces + SelfPrefix[Index % 2];
	}
}

template <typename InElementType, typename InAllocator>
FString MakeHeapString(TArray<InElementType, InAllocator>& Input, int32 Index = 0)
{
	FString Result;
	TArray<FString> Prefix;
	Prefix.Init(TEXT(""), Input.Num());
	MakeHeapPrefix(Prefix);

	const int32 LeftChildIndex = Index * 2 + 1;
	const int32 RightChildIndex = LeftChildIndex + 1;

	if (LeftChildIndex < Input.Num())
	{
		Result += MakeHeapString(Input, LeftChildIndex);
	}
	Result += Prefix[Index] + LexToString(Input[Index]) + TEXT("\n");
	if (RightChildIndex < Input.Num())
	{
		Result += MakeHeapString(Input, RightChildIndex);
	}
	return Result;
}

下面正式开始：

TArray关于堆的函数，有下面这些：

内部调用到的函数，有下面这些，具体代码在BinaryHeap.h中：

下面都以小根堆来为例说明这些函数的实现和怎么用，大根堆只是传入的比较参数不同

Heapify: 将堆初始化为小根堆（或大根堆），也就是所有的父节点都小于（大根堆就是大于）子节点

具体实现就是从最后一个非叶子节点开始做SiftDown操作，一直往前循环到根节点，那么最终得到的就是堆。

HeapSiftDown：代码如上，简单说，就是自顶向下，将数组调整为小根堆。从某个节点开始，比较他和他的两个子节点大小，如果他大于任何一个子节点，就把最小的那个子节点和父节点交换，否则停止。然后再以交换后的子节点为当前节点循环做同样的操作，直到完成整条链。可以看到当做完SiftDown后，从Index开始向下就已经是一个小根堆了。

可以看到，从最后一个非叶子节点开始做SiftDown，循环到根节点，最终整个数组就变成了小根堆，时间复杂度是O(N)，具体的推导证明过程，可以网上搜Heapify的时间复杂度，有挺多讲解的，这里就不说了。

前面那个数组，进行Heapify后，结果如下：

可以看到，每个根节点都小于子节点，也就是这个数组变成了小根堆

HeapPush：将一个元素插入堆到合适位置，并维持小根堆或大根堆

再来看HeapPush具体实现，就是将一个元素插到数组的末尾，接着让这个元素SiftUp

HeapSiftUp：SiftUp操作和SiftDown操作类似，，不同的是自底向上进行循环比较子节点和父节点，一直比较到指定的堆顶为止。可以看到上面插到数组尾部的元素经过SiftUp，最终会向上浮到合适的位置，也会变成一个小根堆。

上面例子再HeapPush一个888，内部会自动调整到合适位置，调整后依然是一个小根堆

结果如下：

HeapPop：将堆顶弹出堆，并维持小根堆或大根堆

具体实现就是将堆顶元素移除掉，将最后一个元素直接挪到堆顶，这时堆顶元素位置不一定在合适的位置，所以对他做SiftDown下沉到一个合适位置

还是上面的例子，做HeapPop

移除了堆顶元素23后，新的堆顶变为了45，这个TArray依然是维持着小根堆

HeapRemoveAt：移除堆中的某个元素，并维持小根堆或大根堆

可以看到，和HeapPop做法一样要先RemoveAtSwap移除对应元素并用末尾元素替换当前位置，但是因为是中间的元素，所以既要SiftDown，完成后还要SiftUp，这样才能保证执行完还是小根堆

示例代码：

HeapSort：堆排序

可以看到，堆排序第一步是建堆，图里代码，比较运算符做了一个反转，也就是从小到大排序要建大根堆，从大到小排序要建小根堆。之后将堆顶和最后一个元素交换，那么可想而知，最后一个元素是最大的。然后堆的大小减1，这时因为堆顶是交换来的最后一个元素，所以SiftDown还原为堆。循环做这个过程后，整个数组就变成了一个从小到大排列的有序数组。复杂度和快速排序是一致的，都是N*log2 N（2为底，N是数量），具体推导可以上网搜，有很多具体讲解的。

然后还是前面那个例子，再来一下：

堆的实际应用

你可能会疑问，觉得堆排序和快速排序复杂度一样，为什么不直接用快速排序呢？实际意义在哪里呢？下面会给一个实际游戏中堆应用的例子。

场景里有10000个怪物，每个怪物都有不同的血量。现在策划提了一个需求，要求程序做一个技能，要求对血量最少的100只怪物造成伤害。那么这里最麻烦的就是怎样从10000只怪物中挑选出血量最少的这100只。

第一反应肯定是对10000个怪物全排序1次，返回前100个就好了。但是我们知道，游戏对性能的要求非常高，这样浪费性能肯定不合适。可以看到用快速排序做全排序的复杂度是10000*log2 10000，一个很大的数字，讲道理也显然不合适。

再仔细分析问题，其实可以看到策划想要的只是前100个，不需要10000个怪物都有序，而且也不要求这100个有序，只要他们是血量最少的就好了，这里的全排序大部分消耗都是白浪费掉的。那么问题就转化为从10000个元素里，挑出100个最小的元素这样的问题。

再结合前面堆排序的用法介绍，可以考虑这样做：

1.首先对10000个元素的数组，前100个元素建大根堆，那么前100个元素中，堆顶肯定是这100个里最大的一个元素。前面有说建堆复杂度是O(n)，那么这里就是O(100)

2.接着从101个开始一直做到10000，和这堆的堆顶做比较，如果比堆顶元素小，那么就将这个数字替换堆顶，并SiftDown。如果比较比堆顶还大，那说明比堆里所有元素都要大，就跳过。这里复杂度可以看到，最理想的情况是每次都跳过，1次都不替换堆顶，时间复杂度就是比较的次数O(N-n)，也就是O(9900)。最终复杂度就是O(N)，也就是O(10000）。最差的情况就是每次都替换并SiftDown，那么时间复杂度就是O((N-n)*log2 n)，也就是O(9900*log2 100)。

3.最终这100个数字就是最小的数字，计算量也远小于全排序。

稍微有一些经验的同学可能会说，快速排序单次操作就能定位到当前数字的真正位置，只要稍微修改一下做法，每次只折半查找小的这一边，直到正好查到位置为100的这个元素，那么他左边的所有元素虽然无序，但已经满足了结果，最终也能做到和上面做法一样的复杂度。并不能说明维护一个堆比快速排序更有优势。

单从上面来看确实如此，但要考虑到游戏运行过程中，怪物的血量可能每帧都在更新，假如每帧都有几只怪物血量发生了变化，那么快速排序每帧都要重新执行一遍。而如果使用上述堆的做法，在第一帧完成建堆之后，不要删除这个堆，接下来的每帧只需要将更新血量的怪物，用同样的方法和当前的堆顶比较，就能达到最终的目的，相比之下还是会比每帧做优化后的快速排序节省了更多的性能。

当然这也只是TArray的函数实际应用的一个例子，具体情况还是要根据业务需求情况灵活选择容器和算法。至少从上面例子来看，TArray提供的堆操作相关函数，确实对上述业务开发提供了非常大的便利。TArray的作者也一定是因为这些函数在实际游戏开发中有广泛的应用场景，才会决定将堆的系列操作函数塞进TArray里。

最后想说的

到这里我对TArray的理解就差不多写完了，整个TArray大部分都是在讲函数介绍，可能基础内容和细节比较多，比较枯燥。但是为什么要写这些东西呢？是因为在我实际的开发项目中，我在做优化性能的工作时，能发现有很多这里面提到的相关性能低下的问题，就只是简单的因为代码写的不注意导致。比如第二篇提到的 RemoveAtSwap和RemoveAt性能上的差别，第一篇提到的MoveTemp用和不用的性能上的差别，就只要改个函数就能让性能提升一个数量级，这种问题改的多了，就想着把这些细节点和经验都记录分享出来。TArray是UE4最简单也是最常用的一个容器，能在自己的代码里用对TArray，就相当于是写对了大部分的逻辑。当然UE4除了TArray外，还有许多容器，许多数据结构和类，比如TSparseArray，TMap, TTripleBuffer等，在仔细研究源码后，一样能找出很多非常精彩的设计和深不见底的坑点，等后续有空了也会记录下来。