Find top k from given array.

You are given an array A of k values which contain int values in sorted (asec) order. Find top k values (asec) which can either be the number from the array A, or sum of any two numbers from A or sum of any three numbers from A. So, if A's values are represented as : a1,a2,...,ak , the possible numbers can be: a(i), a(i)+a(j), a(i)+a(j)+a(l) for any i,j,l < k


Ex: A[7] = {3,4,5,15,19,20,25}
output B[7] = {3,4,5,(3+4),(3+5),(4+5),(3+4+5)}


create a min-heap out of array A,
now get the root, ie 3, and do min-heapify.
after that again get the root ie 4, add it to the rest of the elements seen so far and push back on min-heap.
so in output we have 3, 4
heap we have 5, 7, 15, 19, 20, 25
get the root, add it to each element of the outpu array and push the result back on heap.
also take 2 elements at a time from the array and add it to 5 and push back the result on min-heap and heapify.
output we have now, 3, 4, 5
pushing on heap - (3+5), (4+5) (3+4+5)
heap is now: 7, 8, 9, 12, 15, 19, 20, 25


again get the root and do the above steps,


finally we will have the output array as:
3, 4, 5, 7, 8, 9, 12


Total time complexity: 
klogk + k^2

Min and Max heap in Java

Code input/output:

Printing min heap data: 

12 13 14 15 17 19 20 44 45 52 56 58 74 84 

Printing max heap data

84 74 58 56 52 45 44 20 19 17 15 14 13 12 

Find k closest stars in 3D space.

You have a huge set of stars as three dimensional coordinates. How would you find the k closest stars?


Approach:
S1 = {x1,y1,z1};
S2 = {x2,y2,z2};
S3 = {x3,y3,z3}; and so on..


1. First sort S[1..n] according to x coordinate. Then for every S[i] find the distance from k points in the front and then k points in the back by maintaing a max-heap of size k.
2. Secondly sort S[1..n] according to y coordinate. Then for every S[i] find the distance from k points in the front and k points in tha back and updating the k-size max-heap defined above if required.
3. Now sort S[1..n] according to z coordinate. And for every S[i] find the distance from k points in the front and k points in tha back and update the k-size max-heap if required.
4. Finally, k sized max-heap is the closed k stars.


Total complexity: 3nlogn + 6kn + 5klogk.
Considering k << n, we have: O(nlogn).

Number of min-heaps from an array of size n.

Given an array 1 to N , how many permutations of it will be Min -Heap of of N! possible permutations.


Approach:


Recurrence equation:
T(n) = T(k) * T(n-k-1) * (n-1)Ck where k = number of nodes on left


We always have to take care that the Max-Height(left-subtree) - Max-Height(right-subtree) <= 1.


number of leafs in a heap of size n = Math.floor((n+1)/2).


T(1) = 1
T(2) = 1
T(3) = 2


T(4) = 3C2 * T(2) * T(1) = 3
T(5) = 4C3 * T(3) * T(1) = 8
T(6) = 5C3 * T(3) * T(2) = 20
T(7) = 6C3 * T(3) * T(3) = 80


T(8) = 7C4 * T(4) * T(3) = 210
T(9) = 8C5 * T(5) * T(3) = 896
T(10) = 9C6 * T(6) * T(3) = 3360
T(11) = 10C7 * T(7) * T(3) = 19200
T(12) = 11C7 * T(7) * T(4) = 79200
T(13) = 12C7 * T(7) * T(5) = 506880
T(14) = 13C7 * T(7) * T(6) = 2745600
T(15) = 14C7 * T(7) * T(7) = 21964800