COMP 352 Lecture 18: Priority Queue (Continued)
14 Mar 2016
School
Department
Course
Professor
Document Summary
Transfer the input from an input list to a pq. Remove the minimum or maximum (depending on whether it is max/min pq) from the pq. Insert to the list (repeat until pq is empty) The switch is done in time complexity of o(logn) - as seen last lecture note. Remove the minimum and insert into empty, as you remove the last element is inserted into root and then heap sort is executed to restore order. In this case it would be down heap. The list tree will become empty and this is done in time complexity of o(n logn) You use the input list to create the heap, this saves on space as opposed to using an auxiliary list. Phase 1: read from input and transfer to the heap, read one part of input as heap and rest as input list. Phase 2: sort commences until the heap is empty and for maximum it would be arranged in increasing order.
