Question

Java Question 5: Count elements in the heap

Write a function that returns the number of elements in a min heap strictly less than a given number.

Method signature: public static int elemNumHeap(PriorityQueue minHeap, int val)

Please also include testers.

Answer 1

========================

JAVA PROGRAM

========================

///////PriorityQueueMinHeap.JAVA///////////////////

import java.util.PriorityQueue;

import java.util.Random;

/**

*Class: PriorityQueueMinHeap

*The class constructs a mean heap of

*integers through priority queue

*The mean heap is constructed with MAX_ELELEMTS

*number of integers , which are bound between 0 to

*value set in BOUND.

*Main program calls elemNumHeap() method with

*a random integer between 0 to BOUND and prints count

*of total integers in minHeap which are strictly

*less than the random integer.

*

*/

public class PriorityQueueMinHeap {

//constants

private static final int MAX_ELELEMTS = 15;

private static final int BOUND = 100;

//main method

public static void main(String[] args){

//Create a PriorityQueue of integers

//indicating a min heap

PriorityQueue<Integer> pq = new PriorityQueue<>();

//Create a Random instance

Random random = new Random();

//iterate through for loop MAX_ELELEMTS number of times

for(int i = 1 ; i <= MAX_ELELEMTS; i++){

//get a random integer between 0 and BOUND(exclusive)

int v = random.nextInt(BOUND);

//System.out.println(v);

pq.add(v);//add v to pq

}

//print the min heap

System.out.println("The mean heap is => ");

System.out.println(pq);

//get a random number between 0 and BOUND (exclusive) to check

int randomNumber = random.nextInt(BOUND);

//call elemNumHeap() method to get the count

int count = elemNumHeap(pq,randomNumber);

//print the count

System.out.println("Total number of elements in min heap "

+ "strictly less than "+randomNumber+" is ="+count);

}

/**

* method: elemNumHeap

* It counts total number of integer in minHeap

* which are strictly less than val

* @param minHeap

* @param val

* @return

*/

public static int elemNumHeap(PriorityQueue<Integer> minHeap, int val){

int count = 0;

for(int currentValue : minHeap){

//check if currentValue is less than val

if(currentValue < val){

count++;//increase the count

}

}

return count;//return

}

}

===================================

OUTPUT

===================================

RUN1

----

The mean heap is =>

[0, 12, 2, 63, 19, 13, 16, 98, 66, 95, 27, 61, 22, 88, 28]

Total number of elements in min heap strictly less than 93 is =13

RUN2

-----

The mean heap is =>

[0, 11, 6, 43, 50, 10, 13, 78, 68, 52, 74, 63, 30, 16, 93]

Total number of elements in min heap strictly less than 80 is =14

RUN3

-----

The mean heap is =>

[27, 32, 36, 42, 59, 47, 60, 97, 69, 88, 93, 70, 83, 77, 98]

Total number of elements in min heap strictly less than 13 is =0