min-heap

Given k sorted arrays of size n each, merge them and print the sorted output. Example: **Input:** k = 3, n = 4 arr$$$$ = { {1, 3, 5, 7}, {2, 4, 6, 8}, {0, 9, 10, 11}} ; **Output:** 0 1 2 3 4 5 6 7 8 9 10 11 Method 1 - Merging from 1 array to other It does so by using the “merge” routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged. [Read More]

Lets consider the min heap here. Inserting the key k in the given heap. Consider the heap: Insert k at the end of the last level a) If the heap property is not broken you are done. Suppose k = 10. Here 10 is more than 4, hence min-heap property i.e. parent < child is already followed. Hence everything ok. b)If the heap property is broken, then you have to bubble up the added child until heap property is restored. [Read More]