is AVL tree is better than heap for sorting purpose?

Question

for sorting n elements what is better to use AVL tree or heap data structure and why? Can someone explain in brief?

Answer 1

Both of them will work, and both of them support insertions${}^1$ and deletion${}^2$ of the minimum element in $O(\log n)$ worst-case time (where $n$ is the number of elements currently in the data structure).

It really depends what you mean by "better". An AVL tree will have the additional binary-search-tree property that the heaps do not have, and this allows to quickly support other operations (in addition to returning the ones above). For example you can quickly search for any element in the tree (both for its value and its rank). Indeed, the typical use of AVL trees is to implement a dictionary.

Since there isn't really any reason to use an AVL tree for sorting (they are a bit more complex to implement than an heap), you could stick with an heap. See also: heapsort.

---

_{${}^1$ Notice that constructing an AVL tree of $n$ elements by repeated insertions takes $O(n \log n)$ time. You can also construct an heap by repeated insertions in $O(n \log n)$ time but, since the arrangement of the elements in an heap is more relaxed than a BST, this can actually be improved to $O(n)$. For the purpose of sorting this doesn't really matter since its complexity will be subsumed by the one of the subsequent $n$ deletions.}

_{${}^2$ Deletions are not really necessary if an AVL tree is used. Since an AVL tree is a BST, it suffices to return the elements in the same order as they are considered by a symmetric traversal of the tree.}

Answer 2

No it is not. They both have the same running time but the heap is way lighter for a couple of reasons. For the asymptotic running time, note that a heap can be built in linear time meanwhile applying $n$ operations of extract min takes a total of $O(n \log n)$. On the other hand, constructing an AVL tree requires $O(n\log n)$ operations meanwhile traversing it to construct a sorted array takes only linear time. Hence, both have a total running time of $O(n \log n)$.

However, a heap has a way smaller constant factor compared to all the rotations happening in the construction of an AVL-tree. Even though the depth of an AVL-tree is $O(\log n)$, it comes with a huge constant factor compared to the depth of a heap which is at most $\left\lfloor \log n \right\rfloor + 1$.

More importantly, a heap is very cache-friendly and can be very easily implemented in an array. On the other hand, I can imagine building an AVL-tree in an array is quite cumbersome.