**PLEASE DO NOT POST CODE AS THE QUESTION ONLY ASKED FOR DESCRIPTION**

**PLEASE IGNORE THIS IF YOU CAN NOT GIVE THE DESCRIPTION**

**THE CHAPTER IS ON BASIC DATA STRUCTURES**

Many airlines have frequent-flyer programs designed to encourage airline customers enrolled in the program to accumulate points (also called miles, kilometers, or segments) which may then be redeemed for air travel especially class upgrade. Points earned under FFPs may be based on the class of fare, distance flown on that airline or its partners, or the amount paid. Any frequent flyer can request an upgrade for his or her up-coming flight based on different priorities, which are determined by frequent flyer status (which can be, in order, silver, gold, and platinum) and then, if there are ties, by length of time in the waiting list. In addition, at any time prior to the flight, a frequent flyer can cancel his or her upgrade request (for instance, if he or she wants to take a different flight), using a confirmation code they got when he or she made his or her upgrade request. When it is time to determine upgrades for a flight that is about to depart, the airport gate personnel informs the system of the number, k, of seats available in first or business class, and it needs to match those seats with the k highest-priority passengers on the waiting list. Describe a system that can process upgrade requests and cancellations in O(log n) time and can determine the k highest-priority flyers on the waiting list in O(k log n) time, where n is the number of frequent flyers on the waiting list.