Section 5.5 provides an asymptotic analysis for the worst-case cost of function buildHeap. Give an exact worst-case analysis for buildHeap.

Transcribed Image Text:

5.5 Heaps and Priority Queues There are many situations, both in real life and in computing applications, where we wish to choose the next "most important" from a collection of people, tasks, or objects. For example, doctors in a hospital emergency room often choose to see next the "most critical" patient rather than the one who arrived first. When scheduling programs for execution in a multitasking operating system, at any given moment there might be several programs (usually called jobs) ready to run. The next job selected is the one with the highest priority. Priority is indicated by a particular value associated with the job (and might change while the job remains in the wait list). When a collection of objects is organized by importance or priority, we call this a priority queue. A normal queue data structure will not implement a prior- ity queue efficiently because search for the element with highest priority will take (n) time. A list, whether sorted or not, will also require (n) time for either in- sertion or removal. A BST that organizes records by priority could be used, with the total of n inserts and n remove operations requiring (n log n) time in the average