Re: location of the smallest element in a max-heap

From: Michael J. Fromberger (Michael.J.Fromberger_at_Clothing.Dartmouth.EDU)
Date: 10/06/04 

Date: Tue, 05 Oct 2004 19:57:35 -0400

In article <4162a5f2.412555575@news.sbtc.net>,
 cri@tiac.net (Richard Harter) wrote:

> On Tue, 05 Oct 2004 00:03:46 -0400, "Michael J. Fromberger"
> <Michael.J.Fromberger@Clothing.Dartmouth.EDU> wrote:
>
> >If you make the assumption that all the keys in your max-heap are
> >distinct, then the smallest key must occur at a leaf. [...]
> >
> >On the other hand, if your keys need not be unique, then it is possible
> >that the smallest key may occur at more than one location, not all of
> >which need to be leaves. For instance, consider this heap:
> >
> > 8
> > / \
> > 5 7
> > /
> > 5
> >
> >The occurrence of key (5) as an immediate child of the root is not a
> >leaf. On the other hand, if the smallest key does occur at an internal
> >node, then you can prove that all the descendants of that node have the
> >same key as the node itself, by reasoning similar in spirit to the above.
>
> Your point is well taken, but it doesn't invalidate the assertion that
> the minimum value must occur in a leaf; rather it points out that it
> could occur both in a leaf node and an internal node.

Of course it could. I said as much in the second paragraph of my
response to the original poster. It is also a simple consequence of my
final paragraph.

> > As a further issue, the OP did not specify a binary heap, binary heaps
> being but a particular type of heap. Your arguments hold generally
> for all heaps, AFAIK.

The arguments I outlined are independent of the arity of the heap; the
argument appeals only to the basic heap order and structure properties,
and (where appropriate) the uniqueness of keys. I used a binary heap as
a graphical example, simply because it is easy to render in text. So,
yes, the same reasoning also applies to heaps of larger degree.

Cheers,
-M 

-- 
Michael J. Fromberger             | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/  | Dartmouth College, Hanover, NH, USA

Relevant Pages

  • Re: location of the smallest element in a max-heap
    ... >> in a leaf node but beyond that you can't really tell. ... k could not occur at an internal node. ... As a further issue, the OP did not specify a binary heap, binary heaps ...
    (comp.programming)
  • Re: [PATCH] Priority heap infrastructure enhancements
    ... dropping a leaf should be sufficiently good enough. ... I want a max heap and losing the root of the heap does not work for me. ... Please read the FAQ at http://www.tux.org/lkml/ ...
    (Linux-Kernel)
  • Re: [PATCH] Priority heap infrastructure enhancements
    ... dropping a leaf should be sufficiently good enough. ... I want a max heap and losing the root of the heap does not work for me. ... once you've finished building the heap, for a heap depth of N I think ...
    (Linux-Kernel)