maxElement():
return A[0]
Heap as a Priority Queue

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

A maxheap provides an implementation of a maxpriority queue and a minheap provides an implementation of a minpriority queue. Here again, we will focus on maxheaps and maxpriority 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 maxheap is at the root, so we simply need to return the first element in the array:
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
, whereA
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 elementA[i]
to the new valuek
, such that the new key is larger than the old key. 
Because increasing a key might violate the maxheap 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
, whereA
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
, whereA
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 ininsert
(in case the implementation does not supportincreaseKey
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 reconstruct the heap (i.e., call thebuildMaxHeap
procedure).