# Heap as a Priority Queue

• We can use a (binary) heap as an efficient implementation of the priority queue.

• A max-heap provides an implementation of a max-priority queue and a min-heap provides an implementation of a min-priority queue. Here again, we will focus on max-heaps and max-priority queues.

## Operations

• In addition to the basic heap operations, we define some additional ones for using heaps as priority queues.

### maxElement

• The maximum element in a max-heap is at the root, so we simply need to return the first element in the array:

maxElement():
return A[0]

### removeMaxElement

• To remove the max element, we can simply swap it with the last element in the array, decrement the size of the array and correct the violation at the root by calling maxHeapify(0).

• Pseudocode for removeMaxElement, where A is the array representing the heap:

removeMaxElement():
max = A[0]
A[0] = A[A.size - 1]
maxHeapify(0)
return return max
• Here is an example of remove the max element from a heap.

### increaseKey

• The increaseKey procedure updates the key of element A[i] to the new value k, such that the new key is larger than the old key.

• Because increasing a key might violate the max-heap property, we traverse the path from the node i until the root of the tree to find the correct new place for the element.

• Pseudocode for removeMaxElement, where A is the array representing the heap:

increaseKey(i, k):
if k < A[i]:
error "new key is smaller than current key"
A[i] = k
while i ≥ 0 and A[parent(i)] < A[i]:
swap A[i] and A[parent(i)]
i = parent(i)

### insert

• To insert a new element into the max heap, we add the element to the end of the array and then use the increaseKey procedure to find the correct place for the element.

• Pseudocode for insert, where A is the array representing the heap:

insert(k):
A.size += 1
A[size - 1] = -∞
increaseKey(size - 1, k)

We can expand the call to increaseKey to include the code in insert (in case the implementation does not support increaseKey operation):

insert(k):
A.size += 1
A[size - 1] = k
i = size - 1
while i ≥ 0 and A[parent(i)] < A[i]:
swap A[i] and A[parent(i)]
i = parent(i)
• Here is an example of inserting an element into a heap.

### updatePriorities

• We call updatePriorities when the values of the keys have been changed and the heap property might be violated. So we must assume that we need to re-construct the heap (i.e., call the buildMaxHeap procedure).