Design a food rating system that can do the following:


	Modify the rating of a food item listed in the system.
	Return the highest-rated food item for a type of cuisine in the system.


Implement the FoodRatings class:


	FoodRatings(String[] foods, String[] cuisines, int[] ratings) Initializes the system. The food items are described by foods, cuisines and ratings, all of which have a length of n.

	
		foods[i] is the name of the ith food,
		cuisines[i] is the type of cuisine of the ith food, and
		ratings[i] is the initial rating of the ith food.
	
	
	void changeRating(String food, int newRating) Changes the rating of the food item with the name food.
	String highestRated(String cuisine) Returns the name of the food item that has the highest rating for the given type of cuisine. If there is a tie, return the item with the lexicographically smaller name.


Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

&nbsp;
Example 1:

Input
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]
Output
[null, "kimchi", "ramen", null, "sushi", null, "ramen"]

Explanation
FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]);
foodRatings.highestRated("korean"); // return "kimchi"
                                    // "kimchi" is the highest rated korean food with a rating of 9.
foodRatings.highestRated("japanese"); // return "ramen"
                                      // "ramen" is the highest rated japanese food with a rating of 14.
foodRatings.changeRating("sushi", 16); // "sushi" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "sushi"
                                      // "sushi" is the highest rated japanese food with a rating of 16.
foodRatings.changeRating("ramen", 16); // "ramen" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "ramen"
                                      // Both "sushi" and "ramen" have a rating of 16.
                                      // However, "ramen" is lexicographically smaller than "sushi".


&nbsp;
Constraints:


	1 &lt;= n &lt;= 2 * 104
	n == foods.length == cuisines.length == ratings.length
	1 &lt;= foods[i].length, cuisines[i].length &lt;= 10
	foods[i], cuisines[i] consist of lowercase English letters.
	1 &lt;= ratings[i] &lt;= 108
	All the strings in foods are distinct.
	food will be the name of a food item in the system across all calls to changeRating.
	cuisine will be a type of cuisine of at least one food item in the system across all calls to highestRated.
	At most 2 * 104 calls in total will be made to changeRating and highestRated.


from heapq import heapify, heappop, heappush

class RatedFood:
    def __init__(self, rating, food):
        self.rating = rating
        self.food = food
        
    def __lt__(self, other):
        if other.rating == self.rating:
            return self.food < other.food
        return self.rating < other.rating

class FoodRatings:
    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.cuis_to_score_heap = defaultdict(list)
        self.food_to_latest_ratings = defaultdict(int)
        self.food_to_cuis = defaultdict(str)
        
        for food, cuis, rating in zip(foods, cuisines, ratings):
            self.food_to_cuis[food] = cuis
            self.food_to_latest_ratings[food] = rating
            heappush(self.cuis_to_score_heap[cuis], RatedFood(-rating, food))
        
        

    def changeRating(self, food: str, newRating: int) -> None:
        self.food_to_latest_ratings[food] = newRating
        cuis = self.food_to_cuis[food]
        heappush(self.cuis_to_score_heap[cuis], RatedFood(-newRating, food))
        

    def highestRated(self, cuisine: str) -> str:
        while True:
            ratedFood = heappop(self.cuis_to_score_heap[cuisine])
            if self.food_to_latest_ratings[ratedFood.food] == (-ratedFood.rating):
			
				# because the food item is still valid, we put it back into the heap
                heappush(self.cuis_to_score_heap[cuisine], ratedFood)
				
                return ratedFood.food
class FoodRatings {
    HashMap<String, TreeSet<String>> cuiToFood = new HashMap();
    HashMap<String, Integer> foodToRat = new HashMap();
    HashMap<String, String> foodToCui = new HashMap();
    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        for(int i = 0; i < foods.length; i++){
            TreeSet<String> foodOfThisCuisine = cuiToFood.getOrDefault(cuisines[i], new TreeSet<String> ((a,b)->
            foodToRat.get(a).equals(foodToRat.get(b)) ? a.compareTo(b) : foodToRat.get(b)-foodToRat.get(a)));
			
			// Both comparators are equal
			/* new Comparator<String>(){
                @Override
                public int compare(String a, String b){
                    int aRat = foodToRat.get(a);
                    int bRat = foodToRat.get(b);
                    
                    if(aRat != bRat) return bRat - aRat; // largest rating first
                    for(int i = 0; i < Math.min(a.length(), b.length()); i++){
                        if(a.charAt(i) != b.charAt(i)) return a.charAt(i) - b.charAt(i);
                    }
                    return a.length() - b.length();
                }
            })
			*/
            
            foodToRat.put(foods[i], ratings[i]);
            foodOfThisCuisine.add(foods[i]);
            foodToCui.put(foods[i], cuisines[i]);    
            
            cuiToFood.put(cuisines[i], foodOfThisCuisine);
        }
    }
    
    // CompareTo() is used to compare whether 2 strings are equal in hashSet! So remove, change value of key in HashMap, then insert again
    public void changeRating(String food, int newRating) {
        String cui = foodToCui.get(food);
        TreeSet<String> foodOfThisCui = cuiToFood.get(cui);
        foodOfThisCui.remove(food);
        foodToRat.put(food, newRating);
        
        foodOfThisCui.add(food);
        cuiToFood.put(cui, foodOfThisCui);
    }
    
    public String highestRated(String cuisine) {
        return cuiToFood.get(cuisine).first();
    }
}
class FoodRatings {
public:
    unordered_map<string, set<pair<int, string>>> cuisine_ratings;
    unordered_map<string, string> food_cuisine;
    unordered_map<string, int> food_rating;
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        for (int i = 0; i < foods.size(); ++i) {
            cuisine_ratings[cuisines[i]].insert({ -ratings[i], foods[i] });
            food_cuisine[foods[i]] = cuisines[i];
            food_rating[foods[i]] = ratings[i];
        }
    }
    void changeRating(string food, int newRating) {
        auto &cuisine = food_cuisine.find(food)->second;
        cuisine_ratings[cuisine].erase({ -food_rating[food], food });
        cuisine_ratings[cuisine].insert({ -newRating, food });
        food_rating[food] = newRating;
    }
    string highestRated(string cuisine) {
        return begin(cuisine_ratings[cuisine])->second;
    }
};
var FoodRatings = function(foods, cuisines, ratings) {
  this.heaps = {}, this.foods = {};
  let n = foods.length;
  for (let i = 0; i < n; i++) {
    let food = foods[i], cuisine = cuisines[i], rating = ratings[i];
    if (!this.heaps[cuisine]) this.heaps[cuisine] = new PriorityQueue((a, b) => { // [food, rating]
      return a[1] === b[1] ? a[0].localeCompare(b[0]) : b[1] - a[1];
    })
    this.heaps[cuisine].add([food, rating]);
    this.foods[food] = { cuisine, rating };
  }
};

FoodRatings.prototype.changeRating = function(food, newRating) {
  this.foods[food].rating = newRating;
  let { cuisine } = this.foods[food];
  this.heaps[cuisine].add([food, newRating]);
};

FoodRatings.prototype.highestRated = function(cuisine) {
  let heap = this.heaps[cuisine];
  while (this.foods[heap.top()[0]].rating !== heap.top()[1]) {
    heap.remove();
  }
  return heap.top()[0];
};

class PriorityQueue {
  constructor(comparator = ((a, b) => a - b)) {
    this.values = [];
    this.comparator = comparator;
    this.size = 0;
  }
  add(val) {
    this.size++;
    this.values.push(val);
    let idx = this.size - 1, parentIdx = Math.floor((idx - 1) / 2);
    while (parentIdx >= 0 && this.comparator(this.values[parentIdx], this.values[idx]) > 0) {
      [this.values[parentIdx], this.values[idx]] = [this.values[idx], this.values[parentIdx]];
      idx = parentIdx;
      parentIdx = Math.floor((idx - 1) / 2);
    }
  }
  remove() {
    if (this.size === 0) return -1;
    this.size--;
    if (this.size === 0) return this.values.pop();
    let removedVal = this.values[0];
    this.values[0] = this.values.pop();
    let idx = 0;
    while (idx < this.size && idx < Math.floor(this.size / 2)) {
      let leftIdx = idx * 2 + 1, rightIdx = idx * 2 + 2;
      if (rightIdx === this.size) {
        if (this.comparator(this.values[leftIdx], this.values[idx]) > 0) break;
        [this.values[leftIdx], this.values[idx]] = [this.values[idx], this.values[leftIdx]];
        idx = leftIdx;
      } else if (this.comparator(this.values[leftIdx], this.values[idx]) < 0 || this.comparator(this.values[rightIdx], this.values[idx]) < 0) {
        if (this.comparator(this.values[leftIdx], this.values[rightIdx]) <= 0) {
          [this.values[leftIdx], this.values[idx]] = [this.values[idx], this.values[leftIdx]];
          idx = leftIdx;
        } else {
          [this.values[rightIdx], this.values[idx]] = [this.values[idx], this.values[rightIdx]];
          idx = rightIdx;
        }
      } else {
        break;
      }
    }
    return removedVal;
  }
  top() {
    return this.values[0];
  }
  isEmpty() {
    return this.size === 0;
  }
}
Design a Food Rating System