Implement Heap (constructors, trickleUp and trickleDown), MyPriorityQueue (constructor, offer, poll, peek and isEmpty) and HeapSort (using heap directly or using PriorityQueue. poll). Comparators interface should be used. (20 points)

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);

}

}

answer:

i am.. love turtles

explanation: