这是DSA 2023 Spring PA 4的Kth的解题报告，内容涉及二叉堆。特别地，这篇文章详细解释了如何避免向堆中放入重复的元素。
A.所使用数据结构与算法的构思、原理和实现要点
所使用的数据结构：
二叉堆
算法构思：
1 先利用 compare ，以控制另外两组中数据相同的方式，将三个数组分别排序。
2 利用二叉堆，依次找出前k个小的组合。每次从堆中取出组合(x,y,z)后，向堆中放入与它取值相邻的组合。
实现要点：
1 为了对三个数组各自进行排序，选择自己写一个归并排序。
2 放入点的过程，由于没法使用 hash 或者 bitmap 来避免重复放入，所以需要按照特定的顺序依次放入，直接避免重复放入。
3 由于不能获得数组的原始数据，所以需要存储原数组中序号来代表原数组中的实际数值。
B.完成过程中遇到的问题，排除问题的主要过程、使用的方法和技巧，以及参考资料
问题：如何避免向堆中重复放入组合？
从堆的知识中取得灵感：在堆的使用中，我们不在乎堆中元素是否要完全有序，只在乎父节点和子节点的大小关系。同理，在这个题中，我们不需要在乎堆外元素的入堆顺序，而需要保证堆内元素一定包含当前最小的元素。按“父节点的出堆使子节点入堆”的顺序，可以把元素组织成一棵树。只要这棵树的每一个父节点大于其子节点，算法的正确性就可以得到保障。在这个程序中，我使所有节点(x,y,z)出堆时，引入(x,y,z+1)，只有在z=0时，额外引入(x,y+1,z)，在y和z都为0时，额外引入(x+1,y,z)。这样的加入顺序，可以确保所有堆外的元素，要么在堆外就有元素在所有轴上都不大于它且至少一个轴上小于它，要么在堆内有一个元素比它小。也就是说，当前的最小元素一定出现在堆中。
参考资料
除了习题课PPT，没有参考其他资料。
C.时间和空间复杂度的估算
时间复杂度
堆的规模为k，单次插入和删除复杂度都是O(logk)，由于一共需要进行k次，所以复杂度为O(klogk)。
另一部分无法忽略的时间消耗，是对三个数组分别进行归并排序的过程。复杂度为O(nlogn)。
综上，总体时间复杂度为O(klogk+nlogn)。
空间复杂度
程序中使用的都是定长数组。如果用实际使用空间进行分析的话，二叉堆所实际使用的空间为O(k)，用原数组树的序号来记录大小关系的数组所实际使用的空间为O(n)，所以总体空间复杂度为O(k+n)。