You can use binary heap to implement priority queue by an array. Algorithm for Heapsort: Heap construction. Build max heap using bottom-up method. Sortdown. Repeatedly delete the largest remaining item.
public class Heap
{
public static void sort(Comparable[] a)
{
int N = a.length;
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
while (N > 1)
{
exch(a, 1, N);
sink(a, 1, --N);
}
}
private static void sink(Comparable[] a, int k, int N)
{ }
private static boolean less(Comparable[] a, int i, int j)
{ }
private static void exch(Comparable[] a, int i, int j)
{ }
}
Comleixty: Heapsort: Priority queue:
Processed:
0.010, SQL:
9
