**
4. 1. DecreaseKey(p,d)**

This operation lowers the value of the element at position **p**
by a positive amount **d**. It is used to increase the
priority of an element. We have to find a new
position of the element according to its new priority
by **percolating up**.

**
4. 2. IncreaseKey(p,d)**

This operation increases the value of the element at position
**p** by a positive amount **d**. It is used to
decrease the priority of an element. We have to find a new
position of the element according to its new priority
by **percolating down**.

4. 3. Remove(p)

With this operation an element **p** is removed from the queue.
This is done in two steps:

- Assigning the highest priority to
**p - percolate p up
to the root.**
- Deleting the element in the root and filling the
hole by percolating down the last element
in the queue.

What does it mean to assign the highest priority?

We need to have
a sentinel value for the priorities - a value that is
less than

all possible values assigned as priorities. For example, if
the priorities are positive numbers,

the value 0 will be a sentinel
value.

4. 4. BuildHeap

This operation takes as input **N** elements and places
them into an empty heap

through successive inserts. The worst case running time is bound by O(NlogN).

However, there is another algorithm to build the binary heap,
that runs in **O(N)** time.

The idea:

Given an array of elements to be inserted in the heap, treat the array as a
heap with order property violated, and then do operations to fix the order
property.

Let the array A be:

--- 150 80 40 30 10 70 110
100 20 90 60 50 120 140 130

A[1] is the root, A[1] = 150. Its children are A[2] and A[3], the children of
A[2] are A[4] and A[5], etc. The corresponding tree is:

In order to fix the order property we compare the nodes with their children
starting with the rightmost node at the height 1.

- 110 is less that its children - OK
- 70 is not less than its children . 50 is the node to go up one level.
- 10 is OK
- 30 is not less than its children, 20 is the node to go up

After processing the nodes at height 1 we have the following tree:

Next we examine the nodes at height 2:

- 40 is OK
- 80 needs to be percolated down twice.

The new tree will be:

Next we examine the node at height 3 - the root

150 needs to be percolated down three times - until it gets to the bottom

(Double dotted line indicates two percolates)

Now the tree is in order.

Complexity:

The worst case for a node at height **k** is **k** percolations.

Thus at worst the number of operation is equal to the sum of the
heights of
the nodes in the tree.

**Theorem:** For a perfect binary tree of height **h**
containing **N = 2 **^{h+1}
- 1 nodes,

the sum **S** of the heights of the nodes is
**S = 2 **^{h+1} - 1 - (h + 1) = O(N)

**Proof:**

We can see that the tree has 1 node at height **h**,
2 nodes at height **h - 1**, 4
nodes at height **h - 2**, etc. Thus we have:

nodes height

1 (2^{0}) h
2 (2^{1}) h - 1

4 (2^{2}) h - 2

8 (2^{3}) h - 3

…….

2^{h} 0

Hence we have

S = S 2^{i}
(h - i), i = 0 to h

S = h + 2(h - 1) + 4(h - 2)
+ 8 (h - 3) + …. 2^{(h-2).}2 + 2^{(h-1).}1 (1)

Multiply by 2:

2S = 2h + 4(h - 1)
+ 8(h - 2) + 16 (h - 3) + …. 2^{(h-1).}2 + 2^{(h).}1 (2)

Subtract (1) from (2):

S = h -2h + 2 + 4 + 8 + …. 2 ^{h}

= - h - 1 + (2 ^{h+1} -
1)

= (2 ^{h+1} - 1) - (h + 1)

Note: 1 + 2 + 4 + 8 + …. 2 ^{h }= (2 ^{h+1}
- 1)

Hence S = (2 ^{h+1} - 1) - (h + 1)

Hence the complexity of building a heap with N nodes is linear **O(N)**