View on GitHub


This is the lab related content for the module CS2040C (Data structures and Algorithms)

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)

Solution TBA