Consider a file with a large number of Personid name birthda

Consider a file with a large number of Person(id, name, birth-date) records. Assume that users frequently search this file based on a the field id to find the values of name or birthdate for people whose information is stored in the file. Moreover, assume that users rarely update current records or insert new records to the file. Which file structure, heap versus sorted, provides the fastest total running time for users’ queries over this file? Explain your answer

Solution

For the above case I suggest to go with Sorted File Structure:

Reasons:

Sorted Characteristics :
1. Takes O(n) time to print elements in sorted order (Inorder traversal).
2. Search into a sorted array is O(log n). Insertion is O(n) (you have to move all the elements after the one you\'re inserting).
3. Guarantees order (from \"left\" to \"right\")
4. Is good at all finds (O(logN))
5. Have average of O(logn)O(logn) for insertion, deletion, and search.
6. Search for arbitrary elements is O(log(n)).

Heap Characteristics :
1. Search in O(n logn) time.
2. Extracts min element and re-heapifies the array, which makes it do the sorting in O(n logn) time.
3. Just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels.
4. Is better at findMin/findMax (O(1)).
5. Insert is O(logN) for both structures.
6. Have average O(1)O(1) for findMin/findMax and O(logn)O(logn) for insertion and deletion.
7. It is O(n) in general, except for the largest element which is O(1).