我知道链表不是构建堆的合适数据结构。
这里的答案之一(https://stackoverflow.com/a/14584517/5841727)说堆排序可以在O(nlogn)中使用链表完成，这与数组相同。
我认为堆操作会在链表中花费 O(n) 时间，我们需要 (n/2) 堆操作导致 O(n^2) 的时间复杂度。
有人可以告诉如何使用链表实现O(nlogn)复杂性(堆排序)吗？
你提到的Stackoverflow URL只是某人的主张(至少在我写这篇文章的时候)，所以基于假设这是我的答案。大多数情况下，当人们提到"时间复杂度"时，他们指的是无症状分析，并找出算法所花费的时间随着输入大小的增加而忽略所有常量所花费的时间比例。
为了证明 linkedlist 的时间复杂度，让我们假设有一个函数返回给定索引的值(我知道链表不按索引返回)。为了提高此函数的效率，您还需要传入级别，但我们现在可以忽略它，因为它对时间复杂度没有任何影响。
因此，现在归结为分析随着输入大小的增加，时间比例对此函数的影响。现在你可以想象，为了修复(堆积)一个节点，你可能必须遍历3次最多(1.找出与哪一个交换需要一个遍历来比较两个可能的子节点之一，2.回到父节点进行交换3.回到你刚刚交换的那个)。现在，即使您看起来正在执行最大 n/2 遍历 3 次;对于无症状分析，这刚好等于"n"。现在，您必须对日志 n 执行此操作，这与对数组执行此操作的方式完全相同。因此，时间复杂度为 O(n log n)。在维基百科上堆URL的时间复杂度表 https://en.wikipedia.org/wiki/Binary_heap#Summary_of_running_times