7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Note that heaps are usually modelled as trees but implemented as arrays, if not in the way you propose. $\endgroup$ – Raphael Sep 27 '16 at 7:47
14
$\begingroup$

$\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.

$\endgroup$
  • 1
    $\begingroup$ And adding a new element can't be done faster than O (n) in a contiguous array because there are just up to n elements that are in the wrong place and must be moved to a different place, no matter what you do. $\endgroup$ – gnasher729 Sep 27 '16 at 9:23
  • $\begingroup$ I see. @NP-hard So, the main advantage of representing a heap of a sorted array is its access times to min / max values, but the downside is the insertion due to "making room." Conversely, a heap represented as an unsorted array has the advantage of insertion since it only needs to swap elements until heap properties are satisfied again, but comes with a disadvantage of find-min / find-max at O(log n) ? $\endgroup$ – Nick Olinger Sep 27 '16 at 14:25
  • 1
    $\begingroup$ @LindyHop Yes. It is a trade-off. But $\small \texttt{find-min}$ requires only $\small \mathcal{O}(1)$ time; it is $\small \texttt{delete-min}$ that requires $\small \mathcal{O}(\log n)$ time. $\endgroup$ – PSPACEhard Sep 27 '16 at 14:38
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This helps a lot. It would seem that an implementation requiring lots of search / minimal insertions would be best implemented as a sorted array heap; however, a scenario with many insertions would be best fit for a unsorted array heap / binary tree. $\endgroup$ – Nick Olinger Sep 27 '16 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.