algorithm - 链表和数组的堆排序实现

Question

堆排序可以使用链表和数组来实现。

使用链表或数组的理想方法是什么？

使用数组和链表构建堆的时间复杂度是多少？两者都是O(nlogn)吗？

删除的时间复杂度是多少？

Answer 1

对于数组，是O(nlogn)。因为你可以很容易地获取索引 i 处的元素。这个特性使得获取每个节点的父节点和左/右子节点变得容易。删除的时间复杂度为O(lgn)。

对于链表，我认为是另一回事。这取决于您如何定义“下一个”节点。据我所知，它比使用数组更复杂。