A binary min-heap is initially empty. We call its insert() operation N times to add N distinct integers to the heap. How long will this take in the worst case? In the best case? What sequences of values will result in the worst-case or best-case behavior?
Consider a sorted array. Must it be a valid min-heap?
Suppose that we run heapsort on an array that is already sorted. Will any elements move?
Write a function that takes an array and returns True if the array represents a valid binary heap, otherwise False.
Consider a binary min-heap that holds 12 values, with no duplicates.
How many different array positions are possible for the second smallest value in the heap?
How many different array positions are possible for the third smallest value in the heap?
How many different array positions are possible for the fourth smallest value in the heap?
How many different array positions are possible for the largest value in the heap?
Suppose we'd like to write a program that reads any number of integers from standard input, one per line. When the input ends, the program should print out the 1000 largest numbers that were seen, in sorted order. The input might contain millions or billions of integers, even more than will fit in memory. How can we do this efficiently?