Question 56
In a zero-indexed binary heap array, the left child of index i is located at:
For zero-based indexing, the left and right child indices are 2i+1 and 2i+2 respectively, provided those indices are within the array bounds.
In a zero-indexed binary heap array, the left child of index i is located at:
For zero-based indexing, the left and right child indices are 2i+1 and 2i+2 respectively, provided those indices are within the array bounds.
What is the time complexity of extracting the minimum element from a binary min-heap of n elements?
The root is removed, the last element is moved to the root, and sift-down restores heap order along a path whose length is the heap height, O(log n).
Which sorting algorithm is stable in its standard implementation and has O(n log n) worst-case time?
Merge sort divides the input, recursively sorts both halves, and merges them. A stable merge chooses the left item first when keys are equal.
What is the best-case time complexity of bubble sort when an early-exit swap flag is used?
If the input is already sorted, one pass makes n-1 comparisons and no swaps, after which the algorithm stops.
Which sorting algorithm repeatedly selects the smallest remaining element and places it at the next position?
Selection sort scans the unsorted suffix to find its minimum, then swaps that minimum into the next sorted position.