Lab 04
Here is a pdf version of the ppt I covered during the lab. And the codes that I (skimmed through) / (demonstrated live).
content.pdf (The pdf version of the ppt shown)
STLPriorityQueue.cpp (The STL Priority Queue implementation)
BinHeap.cpp (Our own implementation of max binary heap)
Challenge Questions -
Q) Given an array of N integers, find the Kth smallest element in time complexity -
a) O(NlogN) - Using sorting
b) O(NlogN + KlogN) - Using heaps
c) O(N + KlogN) - Heapify fast in O(N)
d) O(N + KlogK) - Keep the heap of size O(K). Part (D) is >= CS3230 level :P
(Note - We do not want a randomised solution, so do not think along the lines of n_th element function in the C++ library)