PQ are used to schedule jobs (max heap) and in event driven simulation (min heap). While quicksort is faster, heap can be used to build PQ. A PQ is a data structure for maintaining a set S of elements each with an associated value called key.

Operations

A max PQ supports:

• insert(s, x): add x to s
• max(s): return el with max key
• extractMax: remove and returns el with max key
• increaseKey(s, x, k) increase key of x to k. k must be >= x curr key.

heapMax

heapMax(A) {
    return A[1]
}

heapMaxExtraction

O(log n)

heapMaxExtraction(A) {
    if A.size < 1 {
        error "underflow"
    max = A[1]
    A[1] = A[A.size]
    A.size--;
    maxHeapify(A, 1);
    return max;
}

heapIncreaseKey

O (log n)

heapIncreaseKey(A, i, key) {
    if key < A[i]
        error "key must be bigger than current element key"
    A[i] = key
    while i > 1 && A[parent(i)] < A[i]
        swap A[i], A[parent(i)]
        i = parent(i)
}

maxHeapInsert(A, key)

O(log n)

maxHeapInsert(A, key) {
    A.size = A.size + 1
    A[A.size] = - inf
    heapIncreaseKey(A, A.size, key)
}