2 votes 2 votes Which of the following data structures would programmer be least likely to use to implement an abstract data type that must include an efficient implementation of the operation " find the maximum"? Ordered array. Binary search. Heap. Ordered linked list. richa116 asked Dec 22, 2015 edited Jan 28, 2016 by makhdoom ghaya richa116 994 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply monanshi commented Dec 23, 2015 reply Follow Share Is binary search a DS? 4 votes 4 votes srestha commented Dec 23, 2015 reply Follow Share why not? 0 votes 0 votes Shashank Kumar commented Jan 4, 2016 reply Follow Share Here Binary Search => Binary Search Tree which is obviously a data structure. 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes the answer should be d. ordered linked list.(if ordering is done in ascending order then it will take O(n) time to retrieve max value as it need to traverse the link list) the question is asking least likely to be used not most likely. Abhishekcs10 answered Dec 22, 2015 Abhishekcs10 comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Abhishekcs10 commented Dec 24, 2015 i edited by Abhishekcs10 Dec 24, 2015 reply Follow Share there is no need to search since the array is sorted(ordered). Just access the last element of array and that is the maximum. and if u mean any k-th smallest element then also O(1)...:p 0 votes 0 votes srestha commented Dec 24, 2015 reply Follow Share ok, min and max will take O(1) and middle element searched in O(n). 0 votes 0 votes Pranay Datta 1 commented Dec 25, 2015 reply Follow Share if linked list ascending then O(n) but if descending then O(1) , the question does not say anything about it . and about binary search they does not tell that we are applying it on a order list or a unordered list if ordered list then O(logn) if not then it may or may not able to find the max value , then binary search will be the least likely to use . 0 votes 0 votes Please log in or register to add a comment.
–2 votes –2 votes I think it will be array (A) Array could take O(n) time (B) Binary search takes O(log n) times (C) Heap takes O(n log n) times (D) ordered linked list maximum could take O(n) times srestha answered Dec 22, 2015 edited Dec 23, 2015 by srestha srestha comment Share Follow See all 2 Comments See all 2 2 Comments reply Anurag_s commented Dec 23, 2015 reply Follow Share Heap For max O(1),for building O(n), balancing logn 0 votes 0 votes srestha commented Dec 23, 2015 reply Follow Share yes , but it may not be max heap, it may be min heap. then u have to come leaf node in (log n) times. and then search among leaves in O(n) times, as in heap any one element among leaves could be large. So, it takes O(n log n) times to find maximum in min heap. But in binary search we perform only performed when list is sorted. So, only for finding the element it will take O(log n) times right? 0 votes 0 votes Please log in or register to add a comment.