HERGHELEGIU

Another sort method is the HEAP SORT which uses the heap property.
We can use to sort or for priority queues.

So, if we have the following:

A is a heap

A[0..heapsize[A]-1]

Heap property: A[PARENT(i)] >= A[i]

Height of the heap is the height of the root, THETA(lg n)

where:


int PARENT(i)
{
    return (i-1)/2;
}
 
int LEFT(i)
{
    return 2*i+1;
}
 
RIGHT(i)
    return 2*i+2;


First, we must build A as a heap


BUILD-HEAP(A)
{
    for( int i = (length[A]-2)/2; i >= 0; i--)
        HEAPIFY( A, i, length[A] );
}
 
 
void HEAPIFY( A, i, heapSize ) // the left and right are heaps and we make a heap for i
{
    
    int l = LEFT(i);
    int r = RIGHT(i);
    int largest = i;
    
    if ( l <= heapsize && A[l] > A[i] )
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    
    if ( r <= heapsize && A[r] > A[largest] )
    {
        largest = r;
    }
    
    if (largest != i )
    {
        exchange( A[i] - A[largest] );
        HEAPIFY(A, largest, heapSize );
    }
}


Now we can sort A:

void HEAP-SORT(A) // - time O(n lg n)
{
    BUILD-HEAP(A);
    int heapsize = length[A];
    for( int i = length[A]-1; i>0; i--)
    {
        exchange( A[0] , A[i] );
        heapsize = heapsize-1;
        HEAPIFY(A, 0, heapSize );
    }
}



int HEAP-MAXIMUM(A) //- time THETA(1)
{
    return A[0];
}



HEAP-EXTRACTMAX(A) //- time O(lg n)
{
    if ( heapsize[A] < 1 )
        error "heap underflow"
    
    max = A[0];
    
    A[0] = A[ heapsize[A]-1 ]
    heapsize[A] = heapsize[A]-1;
    
    HEAPIFY(A,0, heapSize[A] );
    
    return max;
}



HEAP-INSERT(A, key) //- time O(lg n)
{
    heapsize[A] = heapsize[A] + 1;
    
    i = heapsize[A];
    while ( i > 0 && A[PARENT(i)] < key )
    {
        A[i] = A[PARENT(i)];
        i = PARENT(i);
    }
    A[i] = key;


Read more about it on Wikipedia