0
$\begingroup$

I'm currently learning about how to implement priority queues using heaps, but I've hit a wall while trying to implement the insertion operation. Assume that the size of the array storing the elements of the heap is n, and the size of the heap is also n. Assume further that we try to insert an element 'x' inside the heap. We would have to increment the heap size by 1, but this would now make the heap size greater than the size of the array, which is unacceptable.

So my question is: how do we deal with this problem. Should we A: simply throw an error (since heap size == array size), or B: increase the size of the array by 1. A huge majority of the programs I've seen online implement A, but I think B would be better. Are there any advantages/disadvantages of using A over B (or vice versa)? Are there any other strategies to solving this problem?

Any help is greatly appreciated.

Improve this question
$\endgroup$
  • $\begingroup$ "A huge majority of the programs I've seen online implement A". Please add one or several popular references that support your claim. $\endgroup$ – John L. May 25 '19 at 5:33
  • $\begingroup$ Actually, writing "a huge majority" may not have been the best thing to put, but here are 3 that I found: algolist.net/Data_structures/Binary_heap/Insertion, geeksforgeeks.org/binary-heap, and sites.cs.ucsb.edu/~teo/cs130a.m15/heap.pdf. I found others that just incremented the heap size by 1 and performed "heapify". $\endgroup$ – Johan von Adden May 25 '19 at 11:43
  • $\begingroup$ So I use your code, and at some point it stops working but returns errors, when there is absolutely nothing wrong with my usage of your code. When I find out, what will I think of your code, and of you? At which very hot place would I wish you to be? Unless by "max capacity" you mean that the capacity is impossible to increase. $\endgroup$ – gnasher729 May 25 '19 at 13:18
  • $\begingroup$ @gnasher729 I'm sorry I don't understand what you mean when you say you use my code. The 3 links I provided are not programs that I wrote (if that's what you mean). I believe max capacity is the total maximum number of elements in the array where the heap is stored in. The programs that I found online mainly implemented method A (which I described in my question above). What you pointed out in your first sentence is what I noticed too, which is why I think method B might be the better way to approach this problem, but I want to know why anyone would implement method A in the first place. $\endgroup$ – Johan von Adden May 25 '19 at 21:59
  • $\begingroup$ @gnasher729 One more thing: I believe max capacity would NOT be allowed to be increased in method A (hence the reason why we would need to output an error if heap size == max capacity and we need to insert an additional element). Max capacity would however be ALLOWED to be increased in method B. $\endgroup$ – Johan von Adden May 25 '19 at 22:03
0
$\begingroup$

I decided to go with option B, as it seems like the more practical thing to do.

Improve this answer
$\endgroup$
  • $\begingroup$ Your answer is not very useful for future visitors.The question itself asked for strategies, but answer represents only your personal preference. $\endgroup$ – Evil Sep 8 '20 at 20:45
  • $\begingroup$ @Evil I went with B because I thought it was the practical thing to do, not because it was my personal preference. Since this was a small program that I wrote, going with B made sense since I could easily increase the heap's size. It wouldn't really have made any sense to display some error message if I could simply increase the heap's size. $\endgroup$ – Johan von Adden Sep 10 '20 at 1:54
0
$\begingroup$

In array-based heap implementations I'm familiar with, it is typical to use array resizing where the new size is a constant multiple of the previous size (a.k.a. ArrayList) to avoid quadratic performance on repeated insertions. You can see this in the implementation of the Java standard library's PriorityQueue class, for example.

Improve this answer
$\endgroup$

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.