\nTo get the first two maximum numbers we can create max-heap<\/strong> of the elements of the array and extract two elements (maximum & second maximum), perform the operations, then insert the new value to the max-heap<\/strong>.<\/p>\nNote<\/strong> – Check for integer overflows, for example consider this array 10000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1, in this our p*3<\/code> value will overflow while calculating so for safeguarding we will apply modulo in each subcalculation as well, ((P\u22173)<\/code>%(10<\/code>9<\/sup>+7)<\/code>\u2212(Q\u22172)<\/code>%(10<\/code>9<\/sup>+7)<\/code>)<\/code>.<\/p>\n<\/blockquote>\nMethod 1 :<\/h4>\n\nIn order to get highest and second highest values every time we can get highest and second highest values in a single traversal. After extracting both the values , perform the operation and add it back to the array, now again find highest and the second highest values. Repeat the process N-1<\/code> times, where N<\/code> is the size of our array.<\/p>\n<\/blockquote>\nMethod 2 :<\/h4>\n\n\n- We need to geneate a max-heap<\/strong> from the elements of array of size
N<\/code> to get the maximum elements.<\/li>\n- In a max-heap<\/strong>, the root always stores the larger value as compared to its left<\/strong> & right<\/strong> subtree, this condition needs to be true for every node. We need to insert each item one by one such that parent is always larger than the item itself. If parent is smaller, then swap the current item with its parent. <\/li>\n
- After generating max-heap<\/strong> now extract<\/strong> the first two elements and perform the operation, then add the new obtained value back to the heap using insert()<\/strong>.<\/li>\n
- Repeat the above process
N-1<\/code> times.<\/li>\n- Print the element, this is our required answer.<\/li>\n<\/ul>\n
extract()<\/strong>: Removes the maximum element from Max-Heap<\/strong>. Time Complexity of this Operation is O(Logn) as this operation needs to maintain the heap property (by calling heapify()<\/strong>) after removing root.<\/p>\nheapify()<\/strong>: Maintains the heap property for each node. If any node does not follow heap property it swaps the node with the node which is smaller ,or greater (in case of max-heap<\/strong>), than the node.<\/p>\nBelow is the algorithm of above approach.<\/p>\n<\/blockquote>\n
Algorithms :<\/h3>\nInsert() :<\/h4>\n\n\n- Insert the item at the last index, and increment the size by 1.<\/li>\n
- Then, check if the inserted item is smaller than its parent,<\/li>\n
- If yes, then swap the inserted item with its parent.<\/li>\n
- If no, then do nothing.<\/li>\n
- Now, go to step
2<\/code> and repeat untill we reach root (first element).<\/li>\n<\/ol>\n<\/blockquote>\nExtract() :<\/h4>\n\n\n- Store the value of the first node of our heap (
temp = heap[0]<\/code> ).<\/li>\n- Replace the root node with the farthest right node (last element).<\/li>\n
- Decrease the size by
1<\/code>. (heap[0] = heap[size-1])<\/code><\/li>\n- Perform heapify<\/strong> starting from the new root. <\/li>\n
- Return the stored value.(temp<\/strong>)<\/li>\n<\/ol>\n<\/blockquote>\n
Heapify ():<\/h4>\n\n\n- if the heap property holds true then you are done.<\/li>\n
- else if<\/li>\n
- replacement node value > its parent nodes value
\nthen swap them, and repeat step 3.<\/li>\n - else<\/li>\n
- swap the replacement node with the largest child node, and
\nrepeat step 3.<\/li>\n<\/ol>\n<\/blockquote>\nExample:<\/h4>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2020\/06\/SQNUM.png\")
<\/p>\n
Solutions:<\/h3>\n\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645098878183-Article_312.png\")
<\/p>\n