A complete binary tree is stored in an array with the root at index 0. What is the index of the parent of the node at index 9?
In the same 0-based array representation, which indices hold the children of the node at index 5?
Which of these arrays is a valid max-heap (0-based, root at index 0)?
In a max-heap of n distinct values, where can the smallest value be?
Starting from an empty max-heap, the values 5, 12, 8, 20, 15, 10 are inserted in that order (each insert appends and sifts up). What is the internal array afterwards?
Starting from an empty min-heap, the values 7, 3, 9, 1, 5, 2 are inserted in that order. What is the internal array afterwards?
The max-heap [90, 70, 80, 30, 60, 50, 40, 10, 20] performs one remove-max. What is the array afterwards?
The value 75 is inserted into the max-heap [90, 70, 80, 30, 60, 50, 40, 10, 20]. How many swaps does sift-up perform?
For a binary heap holding n elements, what are the worst-case costs of peek (look at the root), insert, and removeRoot?
A binary heap contains 100 elements. What is its height (the number of edges on the longest root-to-leaf path)?
The array [3, 9, 2, 1, 4, 5, 8] is turned into a max-heap with the bottom-up build (sift down indices n/2 - 1 down to 0). What is the result?
A bottom-up build is run on an array of n = 10 elements. At which index does the loop start sifting down?
Why does the bottom-up build of a heap cost O(n) while inserting the n elements one at a time costs O(n log n)?
Heap sort is applied to [4, 10, 3, 5, 1]. The build phase produces [10, 5, 3, 4, 1]. What does the array look like after the first swap-and-sift-down pass?
Which statement about heap sort is true?
To sort an array in ascending order in place, heap sort builds which kind of heap, and why?
What does this print?
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(8); pq.add(3); pq.add(5);
System.out.println(pq.poll() + " " + pq.peek());
What does this print?
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[] {5, 1, 4, 2, 3}) {
pq.add(x);
}
System.out.println(pq);
What does this print?
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[] {6, 2, 8, 2, 5}) pq.offer(x);
for (int x : pq) {
System.out.print(x + " ");
}
What does this print?
PriorityQueue<String> pq = new PriorityQueue<>(Comparator.reverseOrder());
pq.add("pear"); pq.add("apple"); pq.add("fig"); pq.add("kiwi");
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
What does this print?
PriorityQueue<String> pq = new PriorityQueue<>(
Comparator.comparing(String::length)
.thenComparing(Comparator.naturalOrder()));
pq.add("pear"); pq.add("fig"); pq.add("banana"); pq.add("kiwi"); pq.add("date");
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
What does this print?
int[] data = {7, 2, 9, 4, 9, 1, 6};
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : data) {
heap.offer(x);
if (heap.size() > 3) heap.poll();
}
System.out.println(heap.peek());
You need the k largest of n numbers arriving as a stream (n much larger than k). Using a min-heap that never holds more than k elements, what are the time and extra-space costs?
k sorted lists contain n elements in total. They are merged into one sorted list by keeping one "current" element from each list in a min-heap: poll the smallest, output it, and offer the next element of the same list. What is the running time?
What happens when this code is compiled and run?
PriorityQueue<int[]> pq = new PriorityQueue<>();
pq.add(new int[] {3, 1});
pq.add(new int[] {2, 2});
System.out.println(pq.size());
Explain why a binary heap is stored in a plain array while a general binary tree is usually built from linked Node objects. What property of the heap makes the array representation work, and what does it buy you?
Heap sort is not stable. Give a small concrete input (use labels such as 5a and 5b for equal keys) and trace heap sort far enough to show two equal keys changing their relative order.
To find the 10 largest values in a file of 50 million integers, a student proposes a max-heap that holds all the values, followed by 10 calls to poll(). A classmate proposes a min-heap that never holds more than 10 values. Compare the two approaches in time and memory, and explain why the classmate's heap is a min-heap.
A print server keeps jobs in a java.util.PriorityQueue<Job> ordered by priority (higher first). Users complain that among jobs with the same priority, a job submitted later is sometimes printed before an earlier one. Explain why this happens and write the comparator that fixes it. Job has fields int priority and String owner.
Write a static method boolean isMinHeap(int[] a, int n) that returns true when the first n elements of a form a valid min-heap (root at index 0). It must run in O(n) and must not modify the array. An empty or one-element heap is valid.
Write a generic in-place heap sort
static <E> void heapSort(E[] a, Comparator<? super E> c)
that sorts a into ascending order according to c, using a bottom-up build and a private helper siftDown(E[] a, int i, int n, Comparator<? super E> c). No extra arrays or collections are allowed.