Indexed Min-Priority Queue C++ implementation

A min-priority queue is an abstract data structure that supports efficient query of the minimum element in a list of elements, insertion of elements and deletion of the minimum element. It can be implemented as a min-heap, providing access to the minimum element in O(1), deletion of the minimum element in O(log N) and insertion in O(log N) where N is the number of elements in the heap.

Continue reading

Median of a dynamic list

Here, I discuss the problem of maintaining the running median of a list when numbers are added and removed from the list. The straightforward solution of keeping the list sorted takes constant time per median calculation but linear time per addition/deletion. It would be too slow for our purpose.

Continue reading