0

Heap sort can be implemented using linked list and arrays.

What would be the ideal method of doing it-using linked list or arrays?

What is the time complexity to build heap using arrays and linked lists?Is it O(nlogn) for both?

What is the time complexity for deletion?

4

3 回答 3

2

二叉堆

大 O 表示法的时间复杂度

        Average        Worst case
Space   O(n)           O(n)
Search  N/A Operation  N/A Operation
Insert  O(log n)       O(log n)
Delete  O(log n)       O(log n)

因此，时间复杂度是相同的，与是否使用链表数组无关。

于 2013-01-29T13:52:25.880 回答
2

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

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

于 2013-01-29T13:45:12.523 回答
0

假设实现正确，使用链表或数组的时间复杂度是相同的。

我的博客上有几个堆排序的实现。从这里开始使用传统的基于数组的版本，然后点击链接查看几个链表版本。

于 2013-01-29T13:48:46.337 回答