Problem Statement
A binary heap with the maximum in the root is a heap data structure that takes the form of a binary tree with two additional constraints:
- Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
- Heap property: the key stored in each node is greater than each of the keys in the node's children. (In this problem the keys stored in a heap are always pairwise distinct.)
The ASCII art below shows one possible binary heap with 9 vertices. The numbers represent the keys stored in the vertices of the heap. Note that all heaps with 9 vertices have this exact shape, only the placement of keys into vertices may be different.
100
/ \
19 36
/ \ / \
17 3 25 1
/ \
2 7
Given a heap H, let maxleaf(H) denote the largest key that is stored in one of the leaves of the heap H. E.g., for the heap shown above we have maxleaf(H) = max(2,7,3,25,1) = 25.
You are given the
Definition
- Class:
- BinaryHeapLeaf
- Method:
- maxDiff
- Parameters:
- int
- Returns:
- int[]
- Method signature:
- int[] maxDiff(int N)
- (be sure your method is public)
Constraints
- N will be between 2 and 10^6, inclusive.
Examples
2
Returns: {1, 1 }
The only maximum binary heap with the keys {1, 2} looks as follows: 2 / 1 The only leaf of this heap contains the value 1, so maxleaf(this heap) = 1 and the correct answer is {1, 1}.
3
Returns: {2, 2 }
There are two different maximum binary heaps with the keys {1, 2, 3}: 3 3 / \ and / \ 1 2 2 1 Clearly, both of them have maxleaf = 2, hence the correct answer to this test case is {2, 2}.
4
Returns: {2, 3 }
For N = 4 we have three distinct heaps: 4 4 4 / \ / \ / \ 2 3 3 2 3 1 / / / 1 1 2 The second and third of these heaps have maxleaf = 2, but the one on the left has maxleaf = 3. Thus, the smallest possible value of maxleaf is 2 and the largest is 3, and therefore we should return {2, 3}.
7
Returns: {4, 5 }
Below is one possible heap with maxleaf=4 and one with maxleaf=5. 7 7 / \ / \ 6 5 6 4 / \ / \ / \ / \ 4 1 2 3 3 5 1 2
47
Returns: {24, 43 }
5
Returns: {3, 4 }
6
Returns: {3, 4 }
8
Returns: {4, 6 }
9
Returns: {5, 7 }
10
Returns: {5, 8 }
11
Returns: {6, 9 }
12
Returns: {6, 10 }
44
Returns: {22, 40 }
77
Returns: {39, 72 }
1020
Returns: {510, 1012 }
1021
Returns: {511, 1013 }
1022
Returns: {511, 1013 }
1023
Returns: {512, 1014 }
1024
Returns: {512, 1015 }
1025
Returns: {513, 1016 }
1026
Returns: {513, 1017 }
1027
Returns: {514, 1018 }
1000000
Returns: {500000, 999982 }
999878
Returns: {499939, 999860 }
989765
Returns: {494883, 989747 }
997645
Returns: {498823, 997627 }
997200
Returns: {498600, 997182 }
898988
Returns: {449494, 898970 }
878601
Returns: {439301, 878583 }
789032
Returns: {394516, 789014 }
89
Returns: {45, 84 }
32766
Returns: {16383, 32752 }
30
Returns: {15, 26 }
14
Returns: {7, 11 }
12311
Returns: {6156, 12299 }