📄 http:^^www.cs.wisc.edu^~tick^cs302^week10.1.html
字号:
Date: Wed, 11 Dec 1996 22:33:49 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Fri, 08 Nov 1996 21:54:14 GMTContent-length: 7570<HTML><HEAD><TITLE>CS 302 Section 70 Lecture Notes - Week 10</TITLE></HEAD><BODY><H2><!WA0><!WA0><!WA0><A HREF="http://www.cs.wisc.edu/~tick/cs302.html#text" ><!WA1><!WA1><!WA1><IMG SRC="http://www.cs.wisc.edu/~tick/icons/arrowleft.gif" WIDTH=15 HEIGHT=15></A> Lecture Notes - Week 10,part 1</H2><HR><DL> <DT>Topic: <DD>Heaps <DT>Text: <DD>None. <DT>Notes: <DD> <HR> <DT><H4>Heaps:</H4> <DD>Remember that we've seen binary search represented as a tree, i.e.<p><pre>1 3 5 6 8 9 11becomes 6 / \ 3 9 / \ / \1 5 8 11</pre><p>Where the middle of the search starts with 6. Then if we need to search theleft part of the list, the new middle is 3; if we need to search the right part,though, the middle is 9, and so on down the tree. This is one way that anarray can represent a tree.<p>However, there is another type of tree with an array can represent, calleda heap. There are two things required in order for a tree to be a heap:<OL><LI>It must be a complete tree...Every node must have two children exceptfor the last one, which can have one or two...so the unique complete binarytrees of size 1 through 7 look like<p><pre>o o o o o o o / / \ / \ / \ / \ / \ o o o o o o o o o o o / / \ / \ / / \ / \ o o o o o o o o o o </pre><p><LI>All nodes must satisfy the HEAP PROPERTY [Dramatic Chord]: For each nodein a heap, the value of that node must be >= the value of both children, so<p><pre> 8 / \ 4 2</pre><p>is a heap, whereas<p><pre> 4 / \ 2 8</pre><p>is not.</OL><p>How are heaps represented by arrays? Elements of a heap are read left-to-right,top-to-bottom. So<p><pre> 8 / \ 6 4 / \ / \ 3 5 2 1is stored as8 6 4 3 5 2 1(I'll be referring to this array as LIST from now on)</pre><p><DT><H4>Getting around a heap</H4> <DD>Eventually we'll need to talk about how to obtain a sorted list from aheap. First, though, we need to talk about a few important functions tohelp us move around a heap and change a few values inside.<p><LI><STRONG>Finding related nodes:</STRONG>Note that LIST(1) = 8. Its left childis found at LIST(2). LIST(3) is 4. It's left child is at LIST(6). Ingeneral, given an element N,<UL><LI>The left child of LIST(N) is LIST(2*N).<LI>The right child of LIST(N) is LIST(2*N+1)<LI>The parent of LIST(N) is LIST(N/2) (the inverse of finding a child)</UL><p><LI><STRONG>Heapify:</STRONG> Every once in a while, CS invents a word.The purpose of Heapify ties in to the fact that not every complete binary tree is a heap. We have to worry about whether the heap property is satisfied.Heapify takes a node and moves it down the tree until that node satifiesthe heap property (if it was okay to begin with, it won't be moved at all).<p><pre> 2 / \ 6 4 / \ / \3 5 8 12 6 4 3 5 8 1Suppose we wanted to Heapify node 1 (LIST(1)=2).</pre><p> 2 < 6, so clearly the heap propert is violated. Also, 2 < 4.So we want to move the node down in the tree. So we switch 6 and 2:<pre> 6 / \ 2 4 / \ / \3 5 8 16 2 4 3 5 8 1</pre>We chose 6 because 6 > 4 (if we chose 4, 4 would be at the top with 6 asone of its children, so the heap property would still fail at node 1.<p>We continue to follow the 2, now located at LIST(2). The heap property stillfails there, so we need to switch the 2 and the 5. We get<p><pre> 6 / \ 5 4 / \ / \ 3 2 8 1 6 5 4 3 2 8 1</pre><p>Note that this is still not a heap (the 8 is a problem), but all nodes on thepath from where the 2 was to where the 2 is now satisfy the heap property.<p><LI><STRONG>BuildHeap:</STRONG>We have a way of providing the heap propertyto a path in the tree; now we need to be able to do it to all paths (once it'strue for all paths, then our tree will be a heap).<p> What we're essentially going to do is call heapify within a DO loop. Wewon't need to call Heapify on the bottom nodes (usually called Leaf nodes);Those nodes have no children, so they're as far down as they can go.<p><OL><LI>Start with the the last node that has children (LIST(3), in our exampleabove). In general, if the heap has N elements, this node will be LIST(N/2). <LI>Heapify that node. Then Heapify the node before that in the list (LIST(2)).<LI>Repeat until you reach the top of the tree (LIST(1)).<p> </OL>Example:<p><pre> 2 / \ 4 6 / \ / \1 7 3 8-----------------------------Heapify Node 3 (the 6) 2 / \ 4 8 / \ / \1 7 3 66 < 8, so we had to Heapify, and we chose 8 because 88 > 3. So / \ is a heap. 3 6-----------------------------Heapify Node 2 (the 4) 2 / \ 7 8 / \ / \1 4 3 6 7So / \ is a heap. 1 4 -----------------------------Heapify Node 1 (the 2)This ecompasses 2 moves...2 gets switched withthe 8, then with the 6). 8 / \ 7 6 / \ / \ 1 4 3 2-----------------------------</pre><p>Why start with N/2 and work backwards? Suppose we're given Heaps H1,H2 and aand a node X; the tree<p><pre> X / \ H1 H2</pre><p>can only violate the heap property at one place...X. So if we switchX with the top of H1, then X is fine, H2 is fine, but H1 may not befine. So, let's look at H1.....<p><pre> XH1 now = / \ H3 H4 (H3 and H4 are subheaps)</pre><p>We're back to the same argument we just had above...If X violates theheap property, move in down into H3 or H4. This is exactly what Heapifydoes.<p>So the only node to violate the heap property will always be X. Once heapifyfinds the right spot for X, then even X isn't a problem, so all nodes arefine, and we have our heap.<p>This is why we work back from N/2 to 1. We build heaps out of the lowerparts of the tree, then use them to build a heap out of higher parts ofthe tree. In our example, we made a heap out of the tree starting with LIST(3), then a heap out of the tree starting at LIST(2). We then used thosetwo subheaps to build a heap out of the tree starting with LIST(1).<p><LI><STRONG>HeapSort:</STRONG> Heaps by themselves don't give us a completelysorted array, but they give us a quick method for doing so. Consider the following heap:<p><pre> 8 / \ 4 7 / \ / \ 3 1 2 58 4 7 3 1 2 5</pre><OL><LI>Take the last element in the array and switch it with the first element. Wenow have the largest element in the array at the end of LIST.<LI>Decrease your heap size. So LIST(1) to LIST(7) is the heap; LIST(8)is ignored. Since we've already found the largest number, we don't want toinclude it in our Heap anymore.<p><LI>Heapify LIST(1). We'll get a new Heap based on the first 7 elements ofLIST.<p><pre> 7 / \ 4 5 / \ / 3 1 27 4 5 3 1 2 8</pre><p><LI>Repeat these steps until your heap is empty.<p><pre>so the next time thru, for example, switch 2 and7, decrease your heap size by 1, and Heapify the top. 5 / \ 4 2 / \ 3 15 4 2 3 1 7 8</pre><p>So now the 2 largest elements are in order, at the back of the list. Sowhen you're done, you'll have the entire list is sorted order. </OL><p></DL></BODY><HR><ADDRESS><H5>Copyright © 1996<!WA2><!WA2><!WA2><A HREF="http://www.cs.wisc.edu/~tick/tick.html">Jeff Lampert</A> (<!WA3><!WA3><!WA3><A HREF="mailto:tick@cs.wisc.edu">tick@cs.wisc.edu</A>). Last modified November 8, 1996</ADDRESS></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -