I think that the first thing to consider is what is a supported operation?
Does "inserting a value with a specific, fixed key" (e.g. for keys taken from the integer realm, inserting with key = 3) correspond to a supported operation for the min heap?
No, because that operation can be trivially implemented with more general supported operations. Likewise, inserting 2 elements at once can be done with the exisiting insert
operation.
On the other hand, the insert
operation cannot be defined otherwise than by exposing implementation details. It is pretty much the same for the operations listed on the wikipedia page, heapify
excepted, which could probably be implemented by a sequence of insert
.
In other words, there are elementary operations provided on the type, which are tightly bound to the implementation details for them to be performing well, and there are other operations, which do not abide to that rule, and thus may be implemented as a combinations of the canonical ones.
With that definition in mind, do you think that increase-key could be implemented with other supported operations exlusively, without a loss of performance? If so, then it is not a supported operation by the above definition, otherwise, you may well be right.
Arguably, the definition of a supported operation I provide is mine, as far as I know. It is not formal, and thus subject to discussion (although it seems pretty clear to me). However, I would be glad if someone could provide a source which clearly and unambiguously define what a supported operation is for datatypes, or at least define it in better terms than mine (is that definition given in CLR? I don't have a copy).
My second point will be on how we define a priority queue (which is the raison d'être of binary heaps). Is the increase_key
a necessary operation for that datatype, i.e. for its proper use?
As you can see my angle is all about definitions. I do not really provide an answer to your questions, merely some pointers, so enhancements are welcome.