Answer:
public class HeapSort
{
public void sort(int arr[])
{
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
2. Priority Queue Program
import java.util.Comparator;
import java.util.PriorityQueue;
public class PriorityQueueTest {
static class PQsort implements Comparator<Integer> {
public int compare(Integer one, Integer two) {
return two - one;
}
}
public static void main(String[] args) {
int[] ia = { 1, 10, 5, 3, 4, 7, 6, 9, 8 };
PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>();
for (int x : ia) {
pq1.offer(x);
}
System.out.println("pq1: " + pq1);
PQsort pqs = new PQsort();
PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>(10, pqs);
for (int x : ia) {
pq2.offer(x);
}
System.out.println("pq2: " + pq2);
// print size
System.out.println("size: " + pq2.size());
// return highest priority element in the queue without removing it
System.out.println("peek: " + pq2.peek());
// print size
System.out.println("size: " + pq2.size());
// return highest priority element and removes it from the queue
System.out.println("poll: " + pq2.poll());
// print size
System.out.println("size: " + pq2.size());
System.out.print("pq2: " + pq2);
}
}
