20
$\begingroup$

In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally listed for min-heap? I imagine it is possible to do that in O(height) by iteratively swapping the increased element (x) with the minimum of its children, until none of its children is bigger than x.

e.g.

IncreaseKey(int pos, int newValue)
{
   heap[pos] = newValue;
   while(left(pos) < heap.Length)
   {
      int smallest = left(pos);
      if(heap[right(pos)] < heap[left(pos)])
         smallest = right(pos);
      if(heap[pos] < heap[smallest])
      { 
         swap(smallest, pos);
         pos= smallest;
      }
      else return;
   }   
}

Is the above correct? If not, why? If yes, why isn't increase key listed for min-heap?

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ After reading all the answers, I'd say, it's a strange omission, probably caused by the historically first use of min-heap in the Dijkstra algorithm. $\endgroup$ – maaartinus Sep 29 '14 at 20:28
  • 3
    $\begingroup$ You can of course always implement increase-key using a delete followed by an insert, and delete itself can be implemented as decrease-key (to -∞) followed by delete-min. $\endgroup$ – davmac Nov 14 '16 at 12:11
  • $\begingroup$ @maaartinus comment is the correct answer. $\endgroup$ – max Jun 3 '17 at 10:42
  • $\begingroup$ Everyone seems to just mention Dijkstra's here as a possible explanation, but note that "min-heap" and "decrease-key" are also used together in Prim's MST algorithm, where increase-key is not needed. Surely Prim's algorithm is very similar to Dijkstra's, but conceived even earlier (30's vs late 50's). $\endgroup$ – Amelio Vazquez-Reina 20 hours ago
8
$\begingroup$

The reason that your operation is not listed, is that one is not simply interested in all operations that can be easily implemented using a certain data structure, but rather the other way. Given a set of operations, what is the most efficient way (in terms of space and time) to implement these operations. (But I add more to this later)

Binary heaps implement the abstract data structure priority queue, which asks for operations is_empty, add_element (a key with its priority), find_min, and delete_min. More advanced queues also allow one to decrease the priority of the key (in a min_heap) or even increase it. In fact, you have given an implementation.

Two remarks. Your operation is used in the heapify function, that efficiently constructs a heap from an array. In heapify your operation is repeated (starting from the last key).

Then, most importantly, your code uses the position of the node. For the pure data structure priority queue that is cheating. That data structure asks to perform a certain operation given a key. So in order to decrease or increase the priority of an element, you will first have to locate it. I think that is the main reason it is not listed.

|cite|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ Thanks for the explanation. However, in CLR decrease key also have position as the node as a parameter. $\endgroup$ – GatotPujo Mar 3 '13 at 14:07
  • $\begingroup$ You are right. I could not find a reason for this asymmetry in the definition of Priority queues in Sect.6.5 of CLRS. Note increase-key is not used in Heapsort, the application of this chapter. It seems the asymmetry between increase and decrease is only related to the way the data structure is used in e.g. Dijkstra's algorithm. There (using a min-heap) some selected nodes might become more urgent and are moved 'up' in the heap. $\endgroup$ – Hendrik Jan Mar 4 '13 at 17:02
6
$\begingroup$

The algorithm you suggest is simply heapify. And indeed - if you increase the value of an element in a min-heap, and then heapify its subtree, then you will end up with a legal min-heap.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ then doesn't why CLR or Wikipedia list Increase key to be a supported operation? It kinda misled me to think that it's not possible in a min-heap $\endgroup$ – GatotPujo Mar 2 '13 at 12:58
  • $\begingroup$ I agree that it's misleading, but I don't see any mistake in the algorithm. $\endgroup$ – Shaull Mar 2 '13 at 13:13
0
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ a sample use case can be if I want to maintain a priority queue of object based on least-recently used (e.g. so that I can delete least recently used objects easily). I can use a min-heap with last access date as its key. If an object is accessed, its key will need to be increased. $\endgroup$ – GatotPujo Mar 3 '13 at 14:08
  • $\begingroup$ Very good point. My point of view is a bit limited it seems. Really, @HendrikJan answer brings a very good explanation. $\endgroup$ – didierc Mar 3 '13 at 22:37

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.