educative.io

Which is a better data structure for storing processes in CFS, Red Black Tree or Heap?

Courses
, ,
#1

My understanding of the access patterns for CFS are as below

  • Pick the process with the least vruntime
  • Add a new process
  • Change vruntime of a particular process

For the above access patterns Binary Heap seems to be a better data structure than Red Black Tree due to the time taken for picking the process with the least vruntime.

#2

Binary Heap uses heapify function which takes O(n log n) time. For larger use of heaps, the need for more space can become a hindrance. This happens because heaps are array-based data structures and need contiguous memory.