Custom comparator class for a priority queue?

#1

what is the error ??
can i decide in heap like how the priority or pairs should be defined ???

#2

Hey @hg11110000
Corrected the priority queue definitions : https://ide.codingblocks.com/s/367630
Now try to debug urself.

Yes u can

Incase u haven’t understood the question

We basically need to print top k numbers sorted by frequency when input stream has included k distinct elements, else need to print all distinct elements sorted by frequency.
i can explain you better with examples :-
Input : arr[] = {5, 2, 1, 3, 2}
k = 4
Output : 5 2 5 1 2 5 1 2 3 5 2 1 3 5
Explanation:

  1. After reading 5, there is only one element 5 whose frequency is max till now.
    so print 5.
  2. After reading 2, we will have two elements 2 and 5 with the same frequency.
    As 2, is smaller than 5 but their frequency is the same so we will print 2 5.
  3. After reading 1, we will have 3 elements 1, 2 and 5 with the same frequency,
    so print 1 2 5.
  4. Similarly after reading 3, print 1 2 3 5
  5. After reading last element 2 since 2 has already occurred so we have now a
    frequency of 2 as 2. So we keep 2 at the top and then rest of the element
    with the same frequency in sorted order. So print, 2 1 3 5.

Input : arr[] = {5, 2, 1, 3, 4}
k = 4
Output : 5 2 5 1 2 5 1 2 3 5 1 2 3 4
Explanation:

  1. After reading 5, there is only one element 5 whose frequency is max till now.
    so print 5.
  2. After reading 2, we will have two elements 2 and 5 with the same frequency.
    As 2, is smaller than 5 but their frequency is the same so we will print 2 5.
  3. After reading 1, we will have 3 elements 1, 2 and 5 with the same frequency,
    so print 1 2 5.
    Similarly after reading 3, print 1 2 3 5
  4. After reading last element 4, All the elements have same frequency
    So print, 1 2 3 4.
#3

@Kartikkhariwal1

i have done till k distinct elements…
how to see the next incomming element has a freq in top k elements since how can we get the minimum amaong the top k freq elements ???

#4

Hey @hg11110000
You are pushing multiple copies in ur priority queue ,dont do it like this
Refer to this : https://ide.codingblocks.com/s/328729?_ga=2.233668574.1350203873.1600106484-1795954092.1597348154
And let me know if u dont understand something :slight_smile:

#5

@Kartikkhariwal1

#6

now this seems absolutely correct…pass gives test also…then also wrong ???

i debugged also at each step…seems perfect

then also wrong ???
where i m getting wrong…please help :((

Top k most freq numbers...coding blocks challenges
#7

Here check this
1
3 2
1 1 1
I already told u that u dont have to push multiple copies of same number in priority queue :slight_smile:

#8

ohhh got it now !!

so via this method also can i remove the earliew copy and insert the new copy in pq ?
@Kartikkhariwal1

#9

Yes basically if its already present in map then it means already present in Priority queue so go in prority que find it update i and pushback the rest.

#10

and how u write the compare class @Kartikkhariwal1

i wrote the reverse thinking that it was correct but it was reverse ???

#11

Hey @hg11110000
Refer to this Top K Frequent Word Leetcode

#12

so it works in reverse manner as we write comparator in sort ??? @Kartikkhariwal1
-----------

#13

Yes @hg11110000
…

#14

got it !!!

u r too good in ur explanations brother :slight_smile:

#15

@Kartikkhariwal1…

coz no one told this before

how u come to know about new things concepts btw ?

#16

Hey @hg11110000
Googling concepts is best way to learn if u wanna understand something in detail :slight_smile: .