Why is heapify linear?

[Josiah Carlson]

I am sorry, but in the Python 2.4 description of "heapify", I find the
description of "Transform list x into a heap, in-place, in linear time,"
unbelievable. I understand the hand-wave that makes dictionary building
linear (though I have a hard time with even that). Could somebody tell
me what twist of logic makes "heapify" linear, except in the sense that
linear is coming to mean "very fast?"

It has to do with the amount of work done by doing the heapify operation
from the bottom up.

Using ugly ascii-art math, we get the following work for heapifying from
the bottom up:

log(n) i*n
SUM ----
i=1 2**i

That sum is known to converge to 2n from below (there is a simple
picture that I can present that will prove it to you, if desired). 2n is
O(n). Hence linear.


- Josiah

 

[Scott David Daniels]

I am sorry, but in the Python 2.4 description of "heapify", I find the
description of "Transform list x into a heap, in-place, in linear time,"
unbelievable. I understand the hand-wave that makes dictionary building
linear (though I have a hard time with even that). Could somebody tell
me what twist of logic makes "heapify" linear, except in the sense that
linear is coming to mean "very fast?"

Skeptically,
-Scott David Daniels
(e-mail address removed)

 

[Scott David Daniels]

It has to do with the amount of work done by doing the heapify operation
from the bottom up.

Using ugly ascii-art math, we get the following work for heapifying from
the bottom up:

log(n) i*n
SUM ----
i=1 2**i

That sum is known to converge to 2n from below (there is a simple
picture that I can present that will prove it to you, if desired). 2n is
O(n). Hence linear.


- Josiah

I am feeling incredibly stupid over my post. Of course this is true.
I hadn't considered the triple-at-a-time operation, and I posted w/o
reviewing the code. I'll crawl back in my hole and quietly wipe the
egg off my face.


Embarassedly,
-Scott David Daniels
(e-mail address removed)

 

[Tim Peters]

[Scott David Daniels]

I am sorry, but in the Python 2.4 description of "heapify", I find the
description of "Transform list x into a heap, in-place, in linear time,"
unbelievable. I understand the hand-wave that makes dictionary building
linear (though I have a hard time with even that). Could somebody tell
me what twist of logic makes "heapify" linear, except in the sense that
linear is coming to mean "very fast?"

There are no hands waving. Dict-building is best-case and
expected-case linear time, but worst-case quadratic time. For
heapification, all three are linear. That's all rigorously provable
(and typically are so proved in a first course on algorithmic
complexity). Google on

heapify linear

to find proofs for heapification bounds. But you perhaps won't
*believe* it until you can't deny it <wink>. So try it:

"""
class CmpCounter:
def __init__(self, i):
self.i = i

def __cmp__(self, other):
global cmpcount
cmpcount += 1
return cmp(self.i, other.i)

from heapq import heapify
import random
n = 10000

xs = [CmpCounter(i) for i in range(n)]

def tryone(tag, xs):
global cmpcount
cmpcount = 0
heapify(xs)
print tag, "len", len(xs), "# comparisions", cmpcount

for i in range(10):
random.shuffle(xs)
tryone("random", xs)

xs.sort()
tryone("already sorted", xs)

xs.sort(reverse=True) # using 2.4b1 here
tryone("reverse sorted", xs)
"""

"Already sorted" is essentially the worst case for min-heap
heapification (each new element added is then the smallest seen so
far, and has to bubble all the way from the bottom of the heap-so-far
to the new root location).

Note that "the obvious" way to transform a list into a heap is not
worst-case linear time. Linear-time heapification is due to Floyd.
Someone should patent it <wink>.

 

[Scott David Daniels]

There are no hands waving. Dict-building is best-case and
expected-case linear time, but worst-case quadratic time. For
heapification, all three are linear. That's all rigorously provable
(and typically are so proved in a first course on algorithmic
complexity). Google on

heapify linear

to find proofs for heapification bounds. But you perhaps won't
*believe* it until you can't deny it <wink>. So try it:

I stupidly took a simple look before posting, and a better look
immediately after posting. I feel really stupid for that and
deserve the big clue stick whack.

The "hand wave" on dict building is because I am still stuck in the
sad old world where, when we said O(1), we meant "worst case linear."
I am sure you remember those times. The "expected-case" or "amortized-
time" silent, rather than stated, still bothers me, not so much in an
irritated way, as in a "my mind still doesn't notice" way.

... Note that "the obvious" way to transform a list into a heap is not
worst-case linear time. Linear-time heapification is due to Floyd.

This is the bit I didn't notice, and so my knee-jerk from the "obvious"
way -- essentially a half-sort. As pennance I should read Floyd's paper
(CACM 7, p701, 1964).

 

[Isaac To]

Scott> I am sorry, but in the Python 2.4 description of "heapify",
Scott> I find the description of "Transform list x into a heap,
Scott> in-place, in linear time," unbelievable. I understand the
Scott> hand-wave that makes dictionary building linear (though I
Scott> have a hard time with even that). Could somebody tell me
Scott> what twist of logic makes "heapify" linear, except in the
Scott> sense that linear is coming to mean "very fast?"

I'll try to illustrate the idea without any complex maths, but instead
with real ugly ascii art.

The basic building block of "heapify" is a simple procedure which I'd
call "heapify_node". It looks at a node that is not a leaf, and among
that non-leaf node and its two children, which is largest. Then it
swap that largest node to the top, so that the node becomes the
largest among the three---satisfy the "heap property". Clearly,
constant time.

To heapify the whole tree, we will heapify it from the bottom (so
"bottom up"). Heapifying a node at the "bottom" (i.e., next to a
leaf) is trivial; heapifying a node that is not bottom might cause the
heap property of nodes below to be violated. In that case we will
have to heapify the node below as well, which might cause a node one
more level below to violate heap property. So to heapify a node at
level n, we might need to call heapify_node (height-1) times.

Now we show that a whole run of heapify of a tree with n=2^k-1 nodes
will never call heapify_node more than n times. We do it by finding a
way to charge the calls to heapify_node so that each node is never
charged more than once. Note that we simplify things by always
considering full binary trees (otherwise, the claim has to be a bit
more complicated).

Let's consider the bottom layer. To heapify a node with two children,
we need one call to heapify_node. It is charged to left leaf. So we
have this:

After heapify O
/ \
X O

where O shows a node that is not charged yet, and X show a node which
is already charged. Once all the next-to-bottom nodes have been
heapified, we start to heapify the next-to-next-to-bottom nodes.
Before heapifying a node there, we have

Before heapify O
_/ \_
O O
/ \ / \
X O X O

To heapify this node, we might need two calls to heapify_node. We
charge these two calls to the two uncharged nodes of the left subtree.
So we get:

After heapify O
_/ \_
X O
/ \ / \
X X X O

So none of the nodes is charged more than once, and we still have some
left for the next level, where before heapify the picture is:

Before heapify O
____/ \____
O O
_/ \_ _/ \_
X O X O
/ \ / \ / \ / \
X X X O X X X O

Heapifying at this level requires at most 3 calls to heapify_node,
which are charged again to the left branch. So after that we get

After heapify O
____/ \____
X O
_/ \_ _/ \_
X X X O
/ \ / \ / \ / \
X X X X X X X O

We note a pattern: the path towards the right-most leaf is never
charged. When heapifying a level, one of the branches will always
have enough uncharged nodes to pay for the "expensive" heapify at the
top, while the other branch will still be uncharged to keep the
pattern. So this pattern is maintained until the end of the heapify
procedure, making the number of steps to be at most n-k = 2^k - k - 1.
This is definitely linear to n.

Regards,
Isaac.

 

[Tim Peters]

[Scott David Daniels]

I stupidly took a simple look before posting, and a better look
immediately after posting. I feel really stupid for that and
deserve the big clue stick whack.

I don't know -- it's not obvious that heapification can be done in
worst-case linear time, and indeed that wasn't realized at first.

The "hand wave" on dict building is because I am still stuck in the
sad old world where, when we said O(1), we meant "worst case linear."
I am sure you remember those times. The "expected-case" or "amortized-
time" silent, rather than stated, still bothers me, not so much in an
irritated way, as in a "my mind still doesn't notice" way.

I don't recall much consistency about this no matter how far back we
look, For example, quicksort was always always described as an N log
N sorting method in my experience, despite that its worst case is
quadratic. So I've always qualified O() claims with the intended
measure, unless min, max and mean are the same. For example, finding
the smallest element in a list is O(n) regardless. Since just finding
a minimum is O(n) on its own, it's initially surprising that
heapification is also O(n)!

 

[Scott David Daniels]

Josiah Carlson wrote:

> (there is a simple picture that I can present that will prove it to
> you, if desired).

At which point I became embarassed at not having done my homework before
asking. The sum itself clearly adds to the claimed value, but I hadn't
even read the heapify code yet and was wishing I could hide. I presume
this picture matches Isaac To's ASCII picture.

> [Scott David Daniels]

>> The "hand wave" on dict building is because I am still stuck in the
>> sad old world where, when we said O(1), we meant "worst case linear."

> I don't recall much consistency about this no matter how far back we
> look,

Sorry, the we was more from my personal history (a particular institute
and some of Knuth's classes), not all-of-CS history. I look at O(n) or
linear and think "worst-case," as did everyone in our study groups or
hanging around our education research institute. I wasn't working
towards a doctorate at the time, and only read odd papers for "fun."
I had managed to make a few things infeasibly fast with priority queues
back then, knew their implementation as heaps, and erroneously thought
I knew rough properties.

Isaac To wrote:
<A beautiful explanation of "why linear worst-case">
Thanks, Isaac for writing such a short, clear explanation. I'll still
do the Floyd penance, but now I know the gist and can read for it. The
first exposition of a principle is often not as obviously clear as
subsequent attempts.

-Scott David Daniels
(e-mail address removed)

 

[Josiah Carlson]

Josiah Carlson wrote:

At which point I became embarassed at not having done my homework before
asking. The sum itself clearly adds to the claimed value, but I hadn't
even read the heapify code yet and was wishing I could hide. I presume
this picture matches Isaac To's ASCII picture.

Nope, I (we) do the summation via picture. If you break down each term
(i/2**i) into rows:

1
---
2

1 1
--- ---
4 4

1 1 1
--- --- ---
8 8 8
...

Sum the columns individually:
--- --- ---
1 1/2 1/4

Then sum that bottom row...
1 + 1/2 + 1/4 + 1/8 + 1/16 + ...
A nice geometric sum that approaches 2. Multiply by a factor of n, and
we are done.

I cannot take credit for that picture, I first saw it provided by
Michael Dillencourt (http://www.ics.uci.edu/~dillenco) while I was his
TA.


- Josiah