Why is heap insert O(logN) instead O(n) when you use an array?

Question

I am studying about the arrays vs heap for make a priority queue

For check the heap implementation I am reviewing this code: Heap

, but I have the following question.

Heap is based on array, and for creating an array you need O(n), for inserting into a heap you need O(logN), so if you have a unordered list of task and you want to create a heap, you need O(NLogN).

If you use an array, you need O(n), to create the array, and O(NlogN) to sort the array, so you need O(NLogN).

So if you need implement some similar to this:

function priorityQueue(listOfTask l)

There isn't a diference betwen use an Array or an Heap right? So, why I should use a heap instead an array for solve this function?

Thanks

Answer 1

Keeping a heap is more efficient than keeping a sorted array, when you need to keep adding items to the priority queue. In case you don't need to add to it, you don't need a queue in the first place, just an array sorted by priority.

Insertion to heap-based priority queue is O(logN), while insertion to sorted array is O(N) (binary search for position is O(logN), but inserting there is O(N) ).

As you can see here, almost all data structures are about trade-offs. Converting an array to heap (and keeping it heap) you gain something (O(logN) priority queue action) but also lose something (ability to iterate contents in order, binary search). In contrast, if you used an unsorted array, you'd gain O(1) insertion (because you can just append), but almost everything else would be O(N), which is excellent if you have handful of items, but becomes bad if you have dozens, impossible if you have thousands.

Answer 2

Given your link, you seem to be interested in data structures supporting the following operations:

• Create(m): create a new instance with room for m elements.
• Size(): return the number of elements currently stored in the instance.
• Insert(k): insert an element with priority k.
• ExtractMax(): return the maximal priority currently stored, and remove it.

Since Size() is easy to implement in constant time as part of the other operations, I will not discuss it below.

Here are three sample implementations:

Unsorted array:

• Create() simply allocates memory.
• Insert() simply inserts the element at position i+1, where i is the current number of elements.
• ExtractMax() goes over the entire array, finding the maximum; and then "compacts" the array by moving all elements to the right of the maximum one entry to the left.

Sorted array: (your implementation)

• Create() simply allocates memory.
• Insert() first scans the array to find the proper location for the element, then moves all elements to the right of the intended location one entry to the right, and finally stores the element.
• ExtractMax() returns and removes the ith element, where i is the number of elements currently in the instance.

Binary heap:

• Create() simply allocates memory.
• Insert() and ExtractMax() are described on Wikipedia.

Binary heaps are implemented using "partially sorted" arrays. That is, the order of elements in the array is not arbitrary, but it is also not completely determined. Rather, we are only guaranteed that A[i] ≥ A[2i],A[2i+1]. This freedom allows us to trade-off the running time of the two operations Insert() and ExtractMax().

In all of these implementations, Create() is roughly the same, so to compare the various implementations it suffices to consider the two operations Insert() and ExtractMax():

$$ \begin{array}{c|c|c} \text{Implementation} & \text{Insert()} & \text{ExtractMax()} \\\hline \text{Unsorted array} & O(1) & O(n) \\ \text{Sorted array} & O(n) & O(1) \\ \text{Binary heap} & O(\log n) & O(\log n) \end{array} $$

Here $n$ is the number of elements currently in the array.

If you perform many Insert() and ExtractMax() operations, a binary heap is likely to be more efficient.

Another operation which you mentioned is

• Initialize(A): add to an empty instance the elements in A

You can add support to this operation to all different implementations mentioned above:

• Unsorted array: simply copy A to the array. Running time: $O(|A|)$.
• Sorted array: copy A and sort the resulting array. Running time: $O(|A|\log|A|)$.
• Binary heap: run Insert() for each element of A. Running time: $O(|A|\log|A|)$.

Considering this operation doesn't strengthen the case of your implementation.

Answer 3

A priority queue does something entirely different than sorting an array.

The important operations for a priority queue are: 1. Add an item to the queue. 2. Tell us the smallest item in the queue and remove it from the queue. Both these operations run in O(log n).

Now use a sorted array. Operation 2 is fast if we sorted in descending order. But operation 1 isn’t: Adding a random value to a sorted array and keeping the array sorted requires moving n/2 array elements on average.

You could sort an array in O(n log n) by adding all items to a priority queue, then removing the smallest item n times. Fast sorting algorithms process the array as a whole, they don’t try to keep part of the array sorted (straight insertion or binary insertion do; they ar not fast). Quicksort moves items very roughly into the right place at each step. Note that a priority queue only performs a rough ordering of the items as well. That’s what makes both Quicksort and a priority queue fast: They don’t ask for the data to be sorted at all times.