Example of worst case input for Build-Max-Heap

What would be an example of a worst-case input for Build-Max-Heap? What would the "shape" of it "look like"? I'm having trouble getting a feeling for it.

• There certainly is one. Are you really asking for the shape of one?
– Raphael
Feb 26, 2015 at 13:53
• Yeah. From the answer below, I could only get a partial picture. @Raphael Feb 26, 2015 at 15:15
• In the asymptotic sense, this operation always takes linear time $O(N)$ in the best and the worst case. (Known bounds for the number of comparisons are $1.36443N$ and $1.52128N$.) Apr 27, 2015 at 21:09

Think of a heap as a tree, not its array implementation.

Building a heap work bottom-up. Working from the lowest levels up to the root we add the keys one by one. Worst case is when each key moves as much as possible, so all the way to the level of leaves.

This should start getting the picture.

• I seem to understand by just imagining it but I don't know how to write it out @HendrikJan Feb 27, 2015 at 20:11

Binary Heaps

There are many different ways of implementing a Max Heap, but the simplest (and the one I'm guessing you're interested in) is a binary heap.

A binary heap is just a binary tree, in which the nodes contain the keys of the heap, and we maintain an invariant that the key of a parent node is no smaller than the keys of its children.

Insertion

We can choose to implement insertion in a number of different ways, but again there is a simple choice which I've seen referred to as the "swim" method. Begin by inserting a node at the bottom of the tree. If it's key is larger than its parent's, "swim" it up (exchange it with the parent); otherwise, leave it where it is.

What is the worst case series of inputs for this implementation? The most work we can do per insertion is to move the inserted node all the way up the tree, which translates to $1 + log_2(n)$ compares, where $n$ is the number of nodes already in the tree. Therefore, the worst case sequence of inputs is one sorted in increasing order.

Removing the maximum

A good exercise to test your understanding of these binary heaps might be to answer a similar question to the one you asked. Max Heaps are generally used to implement Max Priority Queues, so in addition to insert we have a method for remove the maximum. A common implementation of remove the maximum involves swapping the max element (the root) with a leaf node, and then "sinking" this leaf down the heap (exchanging it with a child if its key is smaller than that child).

What's the worst case selection of leaves to exchange with the root? Hint: think about the most work we can do in a single remove the maximum operation.