educative.io

How to create a maxheap

Courses
,
#1

How do I write a comparator to sort the queue in descending order? in other words, create a max heap instead min heap?

PriorityQueue<Job> minHeap = new PriorityQueue<Job>(jobs.size(), (a,b)->Integer.compare(a.end, b.end));

What do I replace the below with to make it descending instead of ascending?
(a,b)->Integer.compare(a.end, b.end)

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Problem Challenge 2 - Grokking the Coding Interview: Patterns for Coding Questions

#2

Hi @bee1
A Min-Heap uses the ascending priority while a Max-Heap uses the descending priority. The given solution is designed according to the min heap so we need to change the overall solution. Secondly, if you want to change it according to max heap then you can take the idea from the following code:

class Solution {
public:
struct mycompare
{
bool operator()(const pair<int, string> &p1, const pair<int, string> &p2)
{
return (p1.first<p2.first || (p1.first==p2.first && p1.second>p2.second));

};
vector<string> topKFrequent(vector<string>& words, int k) {
    int n=words.size();
    vector<string> res;
    if(n==1 && k==1)
        res.push_back(words[0]);
    map<string,int> mp;
    int i;
    for(i=0;i<n;i++) {
        if(mp[words[i]]==0)
            mp[words[i]]=1;
        else
            mp[words[i]]++;
    }
    map<string,int> ::iterator it;
    priority_queue<pair<int,string>, vector<pair<int, string>>, mycompare> p;
    for(it=mp.begin();it!=mp.end();it++) {
        p.push(make_pair(it->second,it->first));
    }
    while(k-- && !p.empty()) {
        pair<int,string> t=p.top();
        res.push_back(t.second);
        p.pop();
    }
    return res;
}
};

Hope it will help, Thanks :blush:

1 Like
#3

thx,

I actually did not want to write the algo again. I was just interested in java’s syntax to create a max heap instead of min heap.specifically how to modify this line
(a,b)->Integer.compare(a.end, b.end)

strong text

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Cyclic Sort (easy) - Grokking the Coding Interview: Patterns for Coding Questions

#4

Hi @bee1

My name is Shahrukh Naeem. I hope everything is going well with you. Thank you for reaching out about this. I will try my best to answer your query!

In Java, you can create a max heap or priority queue via one of these methods:

// Method 1 The Collections.reverseOrder() provides a Comparator that would sort the elements in the PriorityQueue in a the opposite order to their natural order
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder()); 
// Method 2
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b - a); 
// Method 3
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b.compareTo(a));

I hope that this guide is helpful. Remember that I am always available via message to help you with any difficulty you might encounter.

Regards,

Happy Learning :slight_smile:

#5

thx @Shahrukh_Naeem
exactly what I was looking for.

2 Likes