Why do we sort through heaps instead of binary search trees?

Question

The heap can be built from a list in O (n logn) time, since inserting an element into the heap takes O (logn) time and n elements.

Similarly, a binary search tree can be constructed from a list in O (n logn) time, since inserting an element into a BST takes average login time and there are n elements.

Moving the heap from min-to-max takes O (n logn) time (because we have to output n elements, and each pop requires an O (logn) immersion operation). Moving a BST from min-to-max takes O (n) time (literally just a workaround).

So, it seems to me that building both structures takes equal time, but BST is faster than iteration. So why do we use "Heapsort" instead of "BSTsort"?

Edit: Thanks to Tobias and lrlreon for your answers! So, below are the points at which we use heaps instead of BST for sorting.

• Heap building can be done in O (n) time, not O (nlogn). This makes the heap construct faster than the BST construct.
• In addition, arrays can easily be converted to heaps in place, because heaps are always full binary trees. BSTs cannot be easily implemented as an array, since BSTs are not guaranteed to be complete binary trees. This means that BST requires additional allocation of O (n) space for sorting, while Heaps only requires O (1).
• All heap operations are guaranteed to be O (logn) time. BST, if they are not balanced, can have O (n) operations. Heaps are significantly easier to implement than balanced BSTs.
• If you need to change the value after creating the heap, all you have to do is apply the shell or swimming operations. Changing a value in a BST is much more conceptually complex.

Answer 1

If the sorting method consists of storing the elements in the data structure and after retrieving in sorting order, then although both approaches (heap and bst) have the same asymptotic complexity O (n log n), the heap tends to be Faster. The reason is that the heap is always a perfectly balanced tree, and its operations are always O (log n) in a deterministic way, and not on average. With bst's, depending on the matching for balancing, insertion and deletion tend to take longer than a bunch, no matter which balancing approach is used. In addition, a heap is usually implemented with an array storing a tree-level traversal, without the need to store any pointers. Thus, if you know the number of elements that usually takes place, the extra storage needed for the heap is less than that used for bst.

When sorting an array, there is a very important reason that would be preferable to a heap than bst: you can use the same array to store the heap; no need to use additional memory.

Answer 2

There are several reasons why I can assume that you want to prefer a (binary) heap over the search tree:

• Construction: The binary heap can actually be built O (n) times by applying heapify operations from bottom to top from smallest to largest subtree.

• Modification: all binary heap operations are pretty simple:

  • Insert item at end? Sift it until the heap condition is met.
  • Did you change the last element to the beginning? Slide it until the heap condition is met.
  • Record key changed? Sift it up or down depending on the direction of change.

• Conceptual simplicity: due to the implicit representation of the array, the binary heap can be implemented by anyone who knows the basic indexing scheme (2i + 1, 2i + 2 - children i), without taking into account many difficult special cases.
  If you look at these operations in a binary search tree, in theory they are also quite simple, but the tree should be stored explicitly, for example. using pointers, and most operations require the tree to be rebalanced to maintain a height of O (log n), which requires complex rotations (red black trees) or splitting / merging nodes (B-trees)

• EDIT: Storage: as Irlan pointed out, you also need more storage space for storing BST, since at least two pointers for children must be stored for each entry in addition to the value itself, which can be a lot of storage overhead, especially for small types of values. At the same time, the heap does not need additional pointers.

To answer the sorting question: BST takes O (n) time to go through in order, the build process takes O (n log n) operations, which, as mentioned earlier, are much more complicated.

At the same time, Heapsort can actually be implemented in place by building the maximum heap from the input array in O (n) time, and then repeatedly changing the maximum element to return and compress the heap. You can think of Heapsort as Insertion sorting with a useful data structure that allows you to find the next maximum in O (log n) time.