SKEDSOFT

HEAP-INCREASE-KEY(A, i, key)

1 if key < A[i]

2   then error "new key is smaller than current key"

3 A[i] ← key

4 while i > 1 and A[PARENT(i)] < A[i]

5     do exchange A[i] ↔ A[PARENT(i)]

6         i ← PARENT(i)

Figure 6.5shows an example of a HEAP-INCREASE-KEY operation. The running time of HEAP-INCREASE-KEY on an n-element heap is O(lg n), since the path traced from the node updated in line 3 to the root has length O(lg n).

Figure 6.5: The operation of HEAP-INCREASE-KEY. (a) The max-heap of Figure 6.4(a) with a node whose index is i heavily shaded. (b) This node has its key increased to 15. (c) After one iteration of the while loop of lines 4-6, the node and its parent have exchanged keys, and the index i moves up to the parent. (d) The max-heap after one more iteration of the while loop. At this point, A[PARENT(i)] ≥ A[i]. The max-heap property now holds and the procedure terminates.

The procedure MAX-HEAP-INSERT implements the INSERT operation. It takes as an input the key of the new element to be inserted into max-heap A. The procedure first expands the max-heap by adding to the tree a new leaf whose key is -∞. Then it calls HEAP-INCREASE-KEY to set the key of this new node to its correct value and maintain the max-heap property.

MAX-HEAP-INSERT(A, key)

1 heap-size[A] ← heap-size[A] 1

2 A[heap-size[A]] ← -∞

3 HEAP-INCREASE-KEY(A, heap-size[A], key)

The running time of MAX-HEAP-INSERT on an n-element heap is O(lg n).

In summary, a heap can support any priority-queue operation on a set of size n in O(lg n) time.