Data Structure for Finding 7th Largest Number

[e(ho0n3]

Another aggrevating question:

Consider the possible data structures for a set of n distinct integers.
i. A min-heap
ii. An array of length n sorted in increasing order
iii. A balanced binary search tree

For which of these data structures is the number of steps need to find and remove the 7th largest element O(log n) in the worst case?

(A) i only (B) ii only (C) i and ii (D) i and iii (E) ii and iii

I know i isn't an answer since the number of steps to find the 7th largest element is O(n log n) in the worst case. That leaves either (B) or (E). Now suppose A[0...n - 1] is representative of data structure ii. Because each A[i] is distinct and A[i] < A[i + 1] for all i (0 to n - 1), the 7th largest element is just A[n - 7]. Removing this element and rearranging does not require O(log n) steps so the answer can't be (B) or (E). The answer given is (E) however. What gives!?

[piero]

Removing this element and rearranging does not require O(log n) steps

Are you confusing O(log n) with Theta(log n)?

For ii: Finding the 7th largest element is O(1). The array is sorted so there is no need for rearrangement. Removing the 7th largest element is also O(1), so all-in-all the worst case is O(1), which is included in O(log n), so ii is ok.

[Magog]

What are the data structures usually that usually appear in the GRE?

[e(ho0n3]

Are you confusing O(log n) with Theta(log n)?

For ii: Finding the 7th largest element is O(1). The array is sorted so there is no need for rearrangement. Removing the 7th largest element is also O(1), so all-in-all the worst case is O(1), which is included in O(log n), so ii is ok.

Silly me. You are right. Thanks.

[e(ho0n3]

What are the data structures usually that usually appear in the GRE?

I think the usual data structures are the ones you learn in a course on data structures.

[e(ho0n3]

Could someone explain how to find the 7th largest element using data structure iii (I'm assuming the tree is not completely balanced)? If h is the height of the tree, then I know the 7th largest element will be in the rightmost sub-tree at height h - 3. At this point, I would have to store the value of every node in this tree in an array (for example), and sort it (using mergesort so I'm guaranteed it will take time O(log n)) to find the 7th largest value. This is the only way I can think of.

[Suhaib1]

I havnt revised this topic yet, but my guess is that to locate 7th largest element the time will be theta (lgn), (more precisely). I am assuming that we have balanced binary tree. ( Your assumption is wrong that 7th largest elemnet appear in the rightmost subtree and at height h-3.The seventh largest element may appear at any position, right,left or at root and at any height depending on the size of tree.).
To search for largest element it requires time O(h=lgn)on balanced tree.and then we can back track to locate the 2nd, 3rd, then 4th,..,7th largest element. All of these searches will only increase the constant term of lgn. and the time to locate the 7th element will remain in order of theta (lgn).

[e(ho0n3]

( Your assumption is wrong that 7th largest elemnet appear in the rightmost subtree and at height h-3.The seventh largest element may appear at any position, right,left or at root and at any height depending on the size of tree.)

I disagree completely. About half of the elements in the tree larger than the root will be on root's right subtree (by definition) and the other half (which is smaller than the root) will be in the root's left subtree. If the root's right subtree has more than six elements, the 7th largest element is guaranteed to be in the root's right subtree.

To search for largest element it requires time O(h=lgn)on balanced tree.and then we can back track to locate the 2nd, 3rd, then 4th,..,7th largest element.

You don't need to search for the largest element in a binary search tree. The largest element will always be the rightmost node in the tree. Also, you can't backtrack to find the other larger elements. For example, the 3rd largest element may be the 1st largest element's parent's left child (i.e. the largest element's sibling). How can you back track to this node?

[Suhaib1]

Yes you are right, almost half of the elements in the tree larger than root are on either side of the root. Now let suppose if we have a complete tree(A complete tree can be a balanced tree) with nodes <15, then the 7th largest element will be the root and incase of this particular tree has size less than 14, then 7th largest element will on the left side of root.because there arent enough number of nodes on the right subtree of root.

The largest element will be the farthest to the right of root. and the second largest will be its parent. For the next we have to see whether this parent has left child, and if it exist then we need to look at this subtree and find 3rd, 4th and so on depending on the number of elements in that subtree and counting, otherwise backtrack to its parent. and do the same.In any case we look at exactly seven elements, and this search will only increase the time complexity by a constant and it will remain order of
O(lgn).
NOTE: I am not familiar with balanced trees, and I assumed that they are similir to complete trees.

[e(ho0n3]

Yes you are right, almost half of the elements in the tree larger than root are on either side of the root. Now let suppose if we have a complete tree(A complete tree can be a balanced tree) with nodes <15, then the 7th largest element will be the root and incase of this particular tree has size less than 14, then 7th largest element will on the left side of root.because there arent enough number of nodes on the right subtree of root.

I repeat, The 7th largest element will be in the rightmost sub-tree at heightt h - 3. If the number of nodes is > 7 and < 15, the height of the tree is 3 and h - 3 = 3 - 3 = 0. This means the rightmost sub-tree starts at the root and as you say, the 7th largest element is in there. There is a special case that I did not cover, which is when there is exactly 7 nodes in the tree, in which case the 7th largest element is the left-most node in the tree. Are you convinced?

The largest element will be the farthest to the right of root. and the second largest will be its parent. For the next we have to see whether this parent has left child, and if it exist then we need to look at this subtree and find 3rd, 4th and so on depending on the number of elements in that subtree and counting, otherwise backtrack to its parent. and do the same.In any case we look at exactly seven elements, and this search will only increase the time complexity by a constant and it will remain order of
O(lgn).

Backtracking seems exceedingly complex. I prefer my simpler method.

NOTE: I am not familiar with balanced trees, and I assumed that they are similir to complete trees.

There are balanced binary trees and complete balanced binary trees. Every node in a complete balanced binary tree has two children, except for the leaves. A balanced binary tree (more specifically a height balanced binary tree) is such that the difference in height of a node's left and right subtree is at most 1.