Heap as a Priority Queue : Pseudo Code

An important use of heap sort is to implement a priority queue. A priority queue is a collection of elements that each element has been assigned a priority and such that order in which elements are deleted and processed comes from the following rules:


1) An element of higher priority is processed before any element of lower priority.
2) Two element with the same priority are processed according to the order in which they were added to the queue.

Pseudo Code :


HeapExtractMax(A){
    if(heap-size[A] < 1){
        //Underflow
    }
    max = A[1];
    A[1] = A[heap-size[A]];
    heap-size[A]--;
    Heapify(A, 1);
    return max;
}

HeapInsert(A, key){     heap-size[A]++;
    i = heap-size[A];
    while(i > 1 && A[Parent(i)] < key){
        A[i] = A[Parent(i)];
        i = Parent(i);
    }
    A[i] = key;
}

Run-Time for HeapExtractMax : O(log n)
Run-Time for HeapInsert : O(log n)