为什么不推荐使用堆对LinkedList进行排序？

我知道如何使用归并排序对链表进行排序，我的问题是，为什么我们不直接使用堆来生成有序的LinkedList？
我的实现思路是：

• 遍历链表，将所有元素依次添加到min-heap中。
• 持续从堆中取出元素，执行heapify操作后将元素添加到新的结果LinkedList中。

我对这个方案的复杂度计算和相关疑问如下：

1. 第一步遍历链表的时间复杂度是O(n)，向堆中添加元素的时间复杂度是O(nlogn)，总时间复杂度为O(nlogn)，如果我的计算有误欢迎指正。
2. 从堆中取出元素的时间复杂度是O(1)，将元素作为下一个节点添加到LinkedList中的时间复杂度是O(1)，如果这个认知有误也欢迎指正。
3. 按照我的理解，这种排序方式的时间复杂度可以达到O(nlogn)，和归并排序的时间复杂度一致。内存方面，我们需要额外使用一个堆，总内存开销我认为是O(nlogn)，而归并排序的内存开销虽然也可以达到O(nlogn)，但可以优化到O(logn)。
4. 这种堆排序的逻辑和“合并k个有序链表”的逻辑一致，这里我假设每个链表只有1个元素。

我对堆方案的复杂度计算可能完全错误，如果有人了解不推荐使用堆的准确原因（也就是为什么归并排序更优），麻烦解释一下。注意这不是堆排序，也不是原地算法。我不太清楚这种方案的时间复杂度会不会是O(n²logn)。

首先先纠正你几个认知上的错误：

• 这个堆方案的整体时间复杂度确实是O(nlogn)，不会到O(n²logn)，你这部分的判断是对的。但你对堆弹出操作的复杂度认知有偏差：获取堆顶最小元素是O(1)，但弹出堆顶后要执行的堆调整（下沉）操作时间复杂度是O(logn)，所以第二步整体的时间复杂度也是O(nlogn)，两步加起来总时间复杂度还是O(nlogn)，和归并排序属于同一复杂度量级。
• 你对堆的空间开销计算错了：存储n个元素的堆只需要O(n)的额外空间，不是O(nlogn)；而链表归并排序如果用递归实现，仅需要O(logn)的递归栈空间，如果用自底向上的迭代实现，甚至可以做到O(1)的额外空间，二者的空间开销差距非常大。

不推荐用堆方案给链表排序，核心原因有几个：

1. 常数时间开销差很多
   堆的每一次插入、弹出操作都需要多次父子节点的数值比较、位置交换，logn的常数项非常高；而链表归并排序的核心操作是合并两个有序链表，仅需要顺序遍历两个链表、比较节点值、修改指针指向，操作非常简单，常数项远低于堆方案，实际运行速度会快很多。
2. 空间开销差距明显
   堆方案需要额外存储所有n个元素的堆结构，不管你存的是节点值还是节点指针，都是O(n)的额外开销；而链表归并排序全程只需要修改原链表的指针，不需要额外存储节点数据，递归版仅需要少量栈空间，迭代版甚至没有额外空间开销，对内存的友好程度高很多。
3. 缓存命中率差距大
   堆一般基于数组实现，如果你在堆中存储的是链表节点指针，那么每次比较节点值的时候都要随机访问不同地址的链表节点，缓存命中率极低；而归并排序是顺序遍历链表，缓存命中率虽然不如数组排序，但也远高于堆方案的随机内存访问。
4. 适配性不如归并
   如果链表存储的是体积较大的自定义对象，堆方案不管是存对象副本还是指针都有额外开销；而归并排序全程只修改指针，完全不需要操作节点存储的实际数据，适配性更高。

至于你提到的和「合并k个有序链表」逻辑一致的点，这个认知是对的，但堆方案仅在k远小于n的时候有优势，当k等于n（也就是每个链表只有1个元素）的场景下，堆方案的优势完全不存在，反而远不如直接用归并排序。

内容的提问来源于stack exchange，提问作者Sanish Joseph