Question

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)

Answer 1

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

}

}