educative.io

Educative

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

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.

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.