[Solved] CSE 310:Week 3 Recitation

1) [10 Pts] Heap and Heap Sort

1. Describe the characteristics of the heap data structure. Explain how heap sort running time becomes theta(nlogn)?

1. Given the following binary tree, show how HEAPIFY(A, 2) works. Cleary show each step

1. Given the following heap, represent the heap in an array named A. clearly how heap sort work on the array A. Clearly show two iterations.

2. [15 Pts] Priority Queue: Suppose you are using the priority queue data structure to maintain plane-landing system. As planes arrive near the vicinity of the airport, each plane sends a landing request with the duration (in minutes) that the plane can wait before landing. For example, plane may send the request with value 30. That means that the plane can wait 30 minutes before landing. Once a landing request is received, the request will be added to the plane landing priority queue. Each time when the land method is called, the landing request with lowest wait time will be removed from the priority queue. Develop a C or C++ program that implements this plane landing system with following user interface

Note: You need to use priority queues algorithms discussed in the class and mentioned in the textbook with required changes in implementing this system (Week 2 Module)

Welcome to the Plane Landing System

1. Make a landing request
2. Land a Plane
3. List all the landing requests
4. Exit

Select your option:

Submission Instructions

Make a PDF file with your answers to question 1 and C or C++ file implementing solutions to question 2. Then make zip file containing your answers to question 1 and question 2.