What is the advantage of heaps over sorted arrays?

Question

I'm fairly new to heaps and am trying to wrap my head around why min and max heaps are represented as trees when a sorted array appears to both provide min / max properties by default.

And a follow up: what is the advantage of dealing with the complexity of inserting into a heap given an algorithm like quick sort handles sorting very well?

Context: I'm working through CLRS / MIT 6.006 in python and have only seen integer representations of leaf values. Is this more applicable in a language like C where each leaf contains a struct that can't easily be sorted?

Answer 1

$\small \texttt{find-min}$ (resp. $\small \texttt{find-max}$), $\small \texttt{delete-min}$ (resp. $\small \texttt{delete-max}$) and $\small \texttt{insert}$ are the three most important operations of a min-heap (resp. max-heap), and they usually have complexity of $\small \mathcal{O}(1)$, $\small \mathcal{O}(\log n)$ and $\small \mathcal{O}(\log n)$ respectively if you implement a min/max-heap by a binary tree.

---

Now suppose instead you implement a min-heap by a sorted (non-decreasing) array (The case for max-heap is similar). $\small \texttt{find-min}$ and $\small \texttt{delete-min}$ are of $\small \mathcal{O}(1)$ complexity if $\small \texttt{insert}$ is not required in your application, since you can maintain a pointer $\small p$ that always points to the minimum element in your array. When the minimum element is removed, you just need to move $\small p$ one step to the next element in the array.

Dealing with insertion in a sorted array is not trivial. Given a new element $\small e$, we can use binary search to locate its position in the array to insert it. But the point is that if you want to insert it there, you have to move a lot of old elements (can be $\small \mathcal{O}(n)$) around to make a vacancy for the new element to reside. This is quite inefficient for most applications. You may also choose to re-sort the array after an element is inserted, this requires $\small \mathcal{O}(n\log n)$ time however.

---

The last point, how you implement a data structure really depends on your application. NO single implementation is best for all cases. Analyze your application, find out the most frequent operations, and then decide the appropriate implementation.

Answer 2

To answer your questions, you have to define which different actions you will perform and how often, and you have to evaluate the time complexity of each action.

Which method is performing better overall will depend on the individual complexities and how often each action is performed.

Sorting an array has a very high time complexity; heap operations are so cheap that they are actually used for a decent sorting implementation. Using a heap to find the smallest element is definitely a lot faster than sorting an array. Two heaps for the smallest and largest element are still a lot faster (but that situation is quite rare; for example in a horse race everyone wants to know the winner, but nobody cares who comes last).

Where a heap absolutely, completely beats sorting arrays is a situation where small numbers of items are removed or added, and after each change you want to know again which is the smallest element.