📄 chap20.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 20: BINOMIAL HEAPS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap21.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap19.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="0862_165c">CHAPTER 20: BINOMIAL HEAPS<a name="0862_165c"></h1><P>
<a name="0862_164b"><a name="0862_164c"><a name="0862_164d"><a name="0862_164e"><a name="0862_164f">This chapter and Chapter 21 present data structures known as <I><B>mergeable heaps</I></B>, which support the following five operations.<P>
<a name="0862_1650"><FONT FACE="Courier New" SIZE=2>MAKE</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>() creates and returns a new heap containing no elements.<P>
<a name="0862_1651"><FONT FACE="Courier New" SIZE=2>INSERT</FONT>(<I>H, x</I>) inserts node <I>x</I>, whose <I>key</I> field has already been filled in, into heap <I>H</I>.<P>
<a name="0862_1652"><FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>(<I>H</I>) returns a pointer to the node in heap <I>H</I> whose key is minimum.<P>
<a name="0862_1653"><FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT>(<I>H</I>) deletes the node from heap<I> H</I> whose key is minimum, returning a pointer to the node.<P>
<a name="0862_1654"><a name="0862_1655"><FONT FACE="Courier New" SIZE=2>UNION</FONT>(<I>H</I><SUB>l</SUB>,<I> H</I><SUB>2</SUB>) creates and returns a new heap that contains all the nodes of heaps <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</SUB>. Heaps <I>H</I><SUB>1</SUB> and <I>H</I><SUB>2</SUB> are "destroyed" by this operation.<P>
In addition, the data structures in these chapters also support the following two operations.<P>
<a name="0862_1656"><FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT>(<I>H, x, k</I>) assigns to node <I>x</I> within heap <I>H</I> the new key value <I>k</I>, which is assumed to be no greater than its current key value.<P>
<a name="0862_1657"><FONT FACE="Courier New" SIZE=2>DELETE</FONT>(<I>H, x</I>) deletes node <I>x</I> from heap <I>H</I>.<P>
As the table in Figure 20.1 shows, if we don't need the <FONT FACE="Courier New" SIZE=2>UNION</FONT> operation, ordinary binary heaps, as used in heapsort (Chapter 7), work well. Operations other than <FONT FACE="Courier New" SIZE=2>UNION</FONT> run in worst-case time <I>O</I>(lg <I>n</I>) (or better) on a binary heap. If the <FONT FACE="Courier New" SIZE=2>UNION</FONT> operation must be supported, however, binary heaps perform poorly. By concatenating the two arrays that hold the binary heaps to be merged and then running <FONT FACE="Courier New" SIZE=2>HEAPIFY</FONT>, the U<FONT FACE="Courier New" SIZE=2>NION </FONT>operation takes <img src="../images/bound.gif">(<I>n</I>) time in the worst case.<P>
In this chapter, we shall examine "binomial heaps," whose worst-case time bounds are also shown in Figure 20.1. In particular, the <FONT FACE="Courier New" SIZE=2>UNION</FONT> operation takes only <I>O</I>(lg <I>n</I>) time to merge two binomial heaps with a total of <I>n</I> elements.<P>
<a name="0862_1658"><a name="0862_1659"><a name="0862_165a"><a name="0862_165b">In Chapter 21, we shall explore Fibonacci heaps, which have even better time bounds for some operations. Note, however, that the running times for Fibonacci heaps in Figure 20.1 are amortized time bounds, not worst-case per operation time bounds.<P>
<pre> Binary heap Binomial heap Fibonacci heap</sub></sup></pre><P>
<pre>Procedure (worst-case) (worst-case) (amortized)</sub></sup></pre><P>
<pre>--------------------------------------------------------------</sub></sup></pre><P>
<pre>MAKE-HEAP <img src="../images/bound.gif">(1) <img src="../images/bound.gif">(1) <img src="../images/bound.gif">(1)</sub></sup></pre><P>
<pre>INSERT <img src="../images/bound.gif">(lg <I>n</I>) <I>O</I>(lg <I>n</I>) <img src="../images/bound.gif">(1)</sub></sup></pre><P>
<pre>MINIMUM <img src="../images/bound.gif">(1) <I>O</I>(lg <I>n</I>) <img src="../images/bound.gif">(l)</sub></sup></pre><P>
<pre>EXTRACT-MIN <img src="../images/bound.gif">(lg <I>n</I>) <img src="../images/bound.gif">(1g <I>n</I>) <I>O</I>(lg <I>n</I>)</sub></sup></pre><P>
<pre>UNION <img src="../images/bound.gif">(<I>n</I>) <I>O</I>(lg <I>n</I>) <img src="../images/bound.gif">(1)</sub></sup></pre><P>
<pre>DECREASE-KEY <img src="../images/bound.gif">(lg<I> n</I>) <img src="../images/bound.gif">(lg <I>n</I>) <img src="../images/bound.gif">(1)</sub></sup></pre><P>
<pre>DELETE <img src="../images/bound.gif">(1g <I>n</I>) <img src="../images/bound.gif">(lg <I>n</I>) <I>O</I>(lg <I>n</I>)</sub></sup></pre><P>
<h4><a name="0862_165d">Figure 20.1 Running times for operations on three implementations of mergeable heaps. The number of items in the heap(s) at the time of an operation is denoted by n.<a name="0862_165d"></sub></sup></h4><P>
This chapter ignores issues of allocating nodes prior to insertion and freeing nodes following deletion. We assume that the code that calls the heap procedures handles these details.<P>
Binary heaps, binomial heaps, and Fibonacci heaps are all inefficient in their support of the operation <FONT FACE="Courier New" SIZE=2>SEARCH</FONT>; it can take a while to find a node with a given key. For this reason, operations such as <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> and D<FONT FACE="Courier New" SIZE=2>ELETE </FONT>that refer to a given node require a pointer to that node as part of their input. This requirement poses no problem in many applications.<P>
Section 20.1 defines binomial heaps after first defining their constituent binomial trees. It also introduces a particular representation of binomial heaps. Section 20.2 shows how we can implement operations on binomial heaps in the time bounds given in Figure 20.1.<P>
<h1><a name="0864_0001">20.1 Binomial trees and binomial heaps<a name="0864_0001"></h1><P>
A binomial heap is a collection of binomial trees, so this section starts by defining binomial trees and proving some key properties. We then define binomial heaps and show how they can be represented.<P>
<h2><a name="0865_1662">20.1.1 Binomial trees<a name="0865_1662"></h2><P>
<a name="0865_165c"><a name="0865_165d"><a name="0865_165e">The <I><B>binomial tree </I></B><I>B<SUB>k</I></SUB> is an ordered tree (see Section 5.5.2) defined recursively. As shown in Figure 20.2(a), the binomial tree <I>B</I><SUB>0</SUB><I> </I>consists of a single node. The binomial tree <I>B<SUB>k</I></SUB> consists of two binomial trees <I>B<SUB>k</I>-1</SUB> that are <I><B>linked</I></B> together: the root of one is the leftmost child of the root of the other. Figure 20.2(b) shows the binomial trees <I>B</I><SUB>0</SUB><I> t</I>hrough <I>B<SUB>4</I></SUB>.<P>
Some properties of binomial trees are given by the following lemma<I>.</I><P>
<img src="402_a.gif"><P>
<h4><a name="0865_1663">Figure 20.2 (a) The recursive definition of the binomial tree B<SUB>k</SUB>. Triangles represent rooted subtrees. (b) The binomial trees B<SUB>o</SUB> through B<SUB>4</SUB>. Node depths in B<SUB>4</SUB> are shown. (c) Another way of looking at the binomial tree B<SUB>k.<a name="0865_1663"></sub></sup></h4><P>
<a name="0865_1664">Lemma 20.1<a name="0865_1664"><P>
<a name="0865_165f">For the binomial tree <I>B<SUB>k</I></SUB>,<P>
1. there are 2<I><SUP>k </I></SUP>nodes,<P>
<a name="0865_1660">2. the height of the tree is <I>k</I>,<P>
3. there are exactly <img src="402_b.gif"> nodes at depth <I>i</I> for <I>i</I> = 0, 1, . . . , <I>k</I>, and<P>
<a name="0865_1661">4. the root has degree <I>k</I>, which is greater than that of any other node; moreover if the children of the root are numbered from left to right by<I> k</I> - 1, <I>k</I> - 2, . . . ,<I> </I>0, child <I>i</I> is the root of a subtree <I>B<SUB>i</I></SUB>.<P>
<I><B>Proof </I></B>The proof is by induction on <I>k</I>. For each property, the basis is the binomial tree <I>B</I><SUB>0</SUB>. Verifying that each property holds for <I>B</I><SUB>0</SUB> is trivial.<P>
For the inductive step, we assume that the lemma holds for <I>B<SUB>k</I>-1</SUB>.<P>
1. Binomial tree <I>B<SUB>k</I></SUB> consists of two copies of <I>B<SUB>k</I>-1</SUB>, so <I>B<SUB>k</I></SUB> has 2<I><SUP>k</I></SUP>-<SUP>1</SUP> + 2<I><SUP>k</I></SUP>-<SUP>1</SUP> = 2<I><SUP>k</I></SUP> nodes.<P>
2. Because of the way in which the two copies of B<I><SUB>k</I>-1 </SUB>are linked to form B<I><SUB>k</I></SUB>, the maximum depth of a node in <I>B<SUB>k</I></SUB> is one greater than the maximum depth in <I>B<SUB>k</I>-1</SUB> . By the inductive hypothesis, this maximum depth is (<I>k</I>-1) + 1 = <I>k</I>.<P>
3. Let <I>D</I>(<I>k, i</I>) be the number of nodes at depth <I>i</I> of binomial tree<I> B<SUB>k</SUB>.</I> Since <I>B<SUB>k</I></SUB> is composed of two copies of <I>B<SUB>k</I>-1</SUB> linked together, a node at depth<I> i </I>in <I>B<SUB>k</I>-1</SUB> appears in <I>B<SUB>k</I></SUB> once at depth <I>i </I>and once at depth <I>i</I> + 1. In other words, the number of nodes at depth <I>i</I> in <I>B<SUB>k</I></SUB> is the number of nodes at depth<I> i</I> in <I>B<SUB>k</I>-1</SUB> plus the number of nodes at depth <I>i</I> - 1 in <I>B<SUB>k</I>-1</SUB> . Thus,<P>
<img src="403_a.gif"><P>
The second equality follows from the inductive hypothesis, and the third equality follows from Exercise 6.1-7.<P>
4. The only node with greater degree in <I>B<SUB>k</SUB> </I>than in <I>B<SUB>k</I>-1</SUB>, is the root, which has one more child than in <I>B<SUB>k</I>-1</SUB>. Since the root of<I> B<SUB>k</I>-1</SUB> has degree <I>k</I>-1, the root of <I>B<SUB>k</I></SUB> has degree <I>k</I>. Now by the inductive hypothesis, and as Figure 20.2(c) shows, from left to right, the children of the root of <I>B<SUB>k</I>-1</SUB> are roots of <I>B<SUB>k</I>-2</SUB>, <I>B<SUB>k</I>-3</SUB>, . . ., <I>B</I><SUB>0</SUB>. When <I>B<SUB>k</I>-1</SUB> is linked to <I>B<SUB>k</I>-1</SUB>, therefore, the children of the resulting root are roots of <I>B<SUB>k</I>-1</SUB>, <I>B<SUB>k</I>-2</SUB>, . . . , <I>B</I><SUB>0</SUB><I> </I> <P>
<a name="0865_1665">Corollary 20.2<a name="0865_1665"><P>
The maximum degree of any node in an <I>n</I>-node binomial tree is lg <I>n</I>.<P>
<I><B>Proof </I></B>Immediate from properties l and 4 of Lemma 20.1. <P>
The term "binomial tree" comes from property 3 of Lemma 20.1, since the terms <img src="403_b.gif"> are the binomial coefficients. Exercise 20.1-3 gives further justification for the term.<P>
<P>
<h2><a name="0866_1664">20.1.2 Binomial heaps<a name="0866_1664"></h2><P>
<a name="0866_1662">A <I><B>binomial heap H</I></B> is a set of binomial trees that satisfies the following <I><B>binomial-heap properties.</I></B><P>
<a name="0866_1663">1. Each binomial tree in <I>H</I> is<I><B> heap-ordered:</I></B> the key of a node is greater than or equal to the key of its parent.<P>
2. There is at most one binomial tree in <I>H</I> whose root has a given degree.<P>
The first property tells us that the root of a heap-ordered tree contains the smallest key in the tree.<P>
The second property implies that an <I>n</I>-node binomial heap <I>H</I> consists of at most <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>lg <I>n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> + 1 binomial trees. To see why, observe that the binary representation of <I>n</I> has <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>lg <I>n</I> <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> + 1 bits, say <img src="../images/lftwdchv.gif"><I>b</I><img src="../images/hfbrdl12.gif"><SUB>lg <I>n</I></SUB><img src="../images/hfbrdr12.gif"><SUB>,<I>b</I></SUB><FONT FACE="Courier New" SIZE=2><SUB><img src="../images/hfbrdl12.gif">lg <I>n</I></SUB><img src="../images/hfbrdr12.gif"> - 1</FONT><SUB> , . . . , <I>b</I></SUB><FONT FACE="Courier New" SIZE=2>0<SUB></SUB><img src="../images/wdrtchv.gif"></FONT>, so that <img src="403_c.gif">. By property 1 of Lemma 20.1, therefore, binomial tree <I>B<SUB><FONT FACE="Courier New" SIZE=2>i </I></FONT></SUB>appears in <I>H</I> if and only if bit <I>b<SUB><FONT FACE="Courier New" SIZE=2>i</I></FONT></SUB> = 1. Thus, binomial heap <I>H</I> contains at most <img src="../images/hfbrdl12.gif">lg <I>n</I><img src="../images/hfbrdr12.gif"> + 1 binomial trees.<P>
<img src="404_a.gif"><P>
<h4><a name="0866_1665">Figure 20.3 A binomial heap H with n = 13 nodes. (a) The heap consists of binomial trees B<SUB>0</SUB>, B<SUB>2</SUB>, and B<SUB>3</SUB>, which have 1, 4, and 8 nodes respectively, totaling n = 13 nodes. Since each binomial tree is heap-ordered, the key of any node is no less than the key of its parent. Also shown is the root list, which is a linked list of roots in order of increasing degree. (b) A more detailed representation of binomial heap H. Each binomial tree is stored in the left-child, right-sibling representation, and each node stores its degree.<a name="0866_1665"></sub></sup></h4><P>
Figure 20.3(a) shows a binomial heap <I>H</I> with 13 nodes. The binary representation of 13 is <img src="../images/lftwdchv.gif">1101<img src="../images/wdrtchv.gif">, and <I>H</I> consists of heap-ordered binomial trees <I>B</I><SUB>3</SUB>,<I> B</I><SUB>2</SUB>, and <I>B</I><SUB>0</SUB>, having 8, 4, and 1 nodes respectively, for a total of 13 nodes.<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -