Date: Wed, 11 Dec 1996 22:33:49 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Fri, 08 Nov 1996 21:54:14 GMT Content-length: 7570 CS 302 Section 70 Lecture Notes - Week 10

Lecture Notes - Week 10,part 1


Topic:
Heaps
Text:
None.
Notes:

Heaps:

Remember that we've seen binary search represented as a tree, i.e.

1 3 5 6 8 9 11

becomes

    6 
   / \
  3   9
 / \ / \
1  5 8  11

Where the middle of the search starts with 6. Then if we need to search the left 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 an array can represent a tree.

However, there is another type of tree with an array can represent, called a heap. There are two things required in order for a tree to be a heap:

  1. It must be a complete tree...Every node must have two children except for the last one, which can have one or two...so the unique complete binary trees of size 1 through 7 look like

    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 
    

  2. All nodes must satisfy the HEAP PROPERTY [Dramatic Chord]: For each node in a heap, the value of that node must be >= the value of both children, so

       8
      / \  
     4   2
    

    is a heap, whereas

       4
      / \
     2   8
    

    is not.

How are heaps represented by arrays? Elements of a heap are read left-to-right, top-to-bottom. So

      8
     / \
    6   4 
   / \ / \
  3  5 2  1

is stored as

8 6 4 3 5 2 1
(I'll be referring to this array as LIST from now on)

Getting around a heap

Eventually we'll need to talk about how to obtain a sorted list from a heap. First, though, we need to talk about a few important functions to help us move around a heap and change a few values inside.

  • Finding related nodes:Note that LIST(1) = 8. Its left child is found at LIST(2). LIST(3) is 4. It's left child is at LIST(6). In general, given an element N,
    • The left child of LIST(N) is LIST(2*N).
    • The right child of LIST(N) is LIST(2*N+1)
    • The parent of LIST(N) is LIST(N/2) (the inverse of finding a child)

  • Heapify: 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 satifies the heap property (if it was okay to begin with, it won't be moved at all).

        2 
       / \
      6   4 
     / \ / \
    3  5 8  1
    
    2 6 4 3 5 8 1
    
    Suppose we wanted to Heapify node 1 (LIST(1)=2).
    

    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:

        6 
       / \
      2   4
     / \ / \
    3  5 8  1
    
    6 2 4 3 5 8 1
    
    We chose 6 because 6 > 4 (if we chose 4, 4 would be at the top with 6 as one of its children, so the heap property would still fail at node 1.

    We continue to follow the 2, now located at LIST(2). The heap property still fails there, so we need to switch the 2 and the 5. We get

         6
        / \
       5   4
      / \ / \
     3  2 8  1 
    
    6 5 4 3 2 8 1
    

    Note that this is still not a heap (the 8 is a problem), but all nodes on the path from where the 2 was to where the 2 is now satisfy the heap property.

  • BuildHeap:We have a way of providing the heap property to a path in the tree; now we need to be able to do it to all paths (once it's true for all paths, then our tree will be a heap).

    What we're essentially going to do is call heapify within a DO loop. We won'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.

    1. Start with the the last node that has children (LIST(3), in our example above). In general, if the heap has N elements, this node will be LIST(N/2).
    2. Heapify that node. Then Heapify the node before that in the list (LIST(2)).
    3. Repeat until you reach the top of the tree (LIST(1)).

    Example:

        2
       / \
      4   6
     / \ / \
    1  7 3  8
    -----------------------------
    Heapify Node 3 (the 6)   
    
        2
       / \
      4   8
     / \ / \
    1  7 3  6
    
    6 < 8, so we had to Heapify, and we chose 8 because 
    
    	    8
    8 > 3. So  / \   is a heap.
              3   6
    -----------------------------
    Heapify Node 2 (the 4)
    
        2
       / \
      7   8
     / \ / \
    1  4 3  6
    
         7
    So  / \   is a heap.
       1   4 
    -----------------------------
    Heapify Node 1 (the 2)
    This ecompasses 2 moves...2 gets switched with
    the 8, then with the 6).
    
         8 
        / \
       7   6 
      / \ / \ 
     1  4 3  2
    -----------------------------
    

    Why start with N/2 and work backwards? Suppose we're given Heaps H1,H2 and a and a node X; the tree

            X
           / \
          H1  H2
    

    can only violate the heap property at one place...X. So if we switch X with the top of H1, then X is fine, H2 is fine, but H1 may not be fine. So, let's look at H1.....

                    X
    H1 now =       / \
                 H3  H4  
    (H3 and H4 are subheaps)
    

    We're back to the same argument we just had above...If X violates the heap property, move in down into H3 or H4. This is exactly what Heapify does.

    So the only node to violate the heap property will always be X. Once heapify finds the right spot for X, then even X isn't a problem, so all nodes are fine, and we have our heap.

    This is why we work back from N/2 to 1. We build heaps out of the lower parts of the tree, then use them to build a heap out of higher parts of the 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 those two subheaps to build a heap out of the tree starting with LIST(1).

  • HeapSort: Heaps by themselves don't give us a completely sorted array, but they give us a quick method for doing so. Consider the following heap:

         8
        / \
       4   7
      / \ / \
     3  1 2  5
    
    8 4 7 3 1 2 5
    
    1. Take the last element in the array and switch it with the first element. We now have the largest element in the array at the end of LIST.
    2. 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 to include it in our Heap anymore.

    3. Heapify LIST(1). We'll get a new Heap based on the first 7 elements of LIST.

           7
          / \
         4   5
        / \ /
       3  1 2
      
      7 4 5 3 1 2 8
      

    4. Repeat these steps until your heap is empty.

      so the next time thru, for example, switch 2 and
      7, decrease your heap size by 1, and Heapify the top. 
      
           5
          / \
         4   2
        / \
       3   1
      
      5 4 2 3 1 7 8
      

      So now the 2 largest elements are in order, at the back of the list. So when you're done, you'll have the entire list is sorted order.


  • Copyright © 1996Jeff Lampert (tick@cs.wisc.edu). Last modified November 8, 1996