17-05-2013, 02:16 PM
Further Data Structures
Data Structures.pdf (Size: 892.44 KB / Downloads: 19)
The story so far
- Saw some fundamental operations as well as advanced
operations on arrays, stacks, and queues
- Saw a dynamic data structure, the linked list, and its
applications.
- Saw the hash table so that insert/delete/find can be
supported efficiently.
- Saw how hierarchical data can be stored in a tree along
with applications.
This week we will
- Introduce a new operation : deleteMin and its
applications.
- Propose data structures for an efficient deleteMin
Motivation
Consider a job scheduling environment
- such as a printer facility
- several jobs accepted
- printed in a certain order. typically, first in first out.
Another example could be an office
- several files to be cleared.
- Which ones are taken up first?
- The order is not entirely FIFO.
Use an Array/Queue
Can store jobs in consecutive indices.
Adding a new job is easy.
But, deleting the job with the highest priority
requires scanning the entire array/queue.
Keeping the array sorted also does not help.
- May use binary search to locate the required job.
- But, deleting an element at some index requires moving
all other elements.
At any rate, cost of insert and delete the job with
highest priority takes O(n) time for n jobs.
Our Solution
Consider a binary tree of n nodes where the leaf
nodes are spread across at most two levels.
This also suggests that the depth of the tree is at
most ceil(log n).
Another way to say the above : the tree is
completely occupied by nodes with the exception
of the last level where nodes are filled from left to
right.