Questions about heaps in coursera's open course

2
votes

Here are two questions that I got the wrong answer but I don't know why.

1.Suppose you implement the functionality of a priority queue using a sorted array (e.g., from biggest to smallest). What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)

My answer is O(log(n)) and O(1) since we can binary search and insert so O(log(n))

extract-min is easy.

but the right answer is O(n) and O(1).

2.Suppose you implement the functionality of a priority queue using an unsorted array. What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)

My answer is O(1) and O(log(n)) since the insert is arbitrary and extract-min we can first sort then take the minimum.

but the right answer is O(1) and O(n)

Could anyone help me with this problem?Thanks a lot.

Oh,I understand the 2nd question,sort takes O(n*log(n)) not O(log(n))

3
algorithmheap

3 Answers

4
votes

  1. The porblem with array is not to find the place where you need to insert the element, it is to actually insert it. It will require you to shift all elements next to it by one index, and this will cost O(n).
    Example: [1,5,8,10,15], you need to insert 4, finding where you need to insert it is easy, but you need to expand the array (that can be done esaily with dynamic arrays), and then push all elements greater than 4 (5,8,10,15) to the right, which will be O(n), and you will get [1, _, 5, 8, 10, 15] - so you can safely add 4 without overriding an existing value.

  2. Now, inserting an element is fairly easy - you just need to push it at the back of the array, it will be O(1) (using dynamic arrays). But, searching for the minimum is going to require a linear scan, which is O(n).

0
votes

For sorted array, you can search the right place for insertion in O(log n), but it requires O(n) for insertion. Because you need to move all elements after the place.

0
votes
  1. you would need to shift the values in the array after the inserted value, hence O(n).
  2. you already pointed out. sorting takes O(n*logn), but you can just use linear scan to find minimum - O(n)