Thread: Heaps...

  1. #1
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020

    Heaps...

    Hi,

    What is a heap? I heard that the heap is a region of memory located to your program by the OS. But what about heap in terms of sorting data? Heap sort. How does it work?

    thnx

  2. #2
    Registered User stautze's Avatar
    Join Date
    Apr 2002
    Posts
    195
    When explaining heaps it is easier to image a tree, but a heap is really just a list.

    You can image a upside down tree of the corporate pecking order. The CEO at the root of the tree. 1st and 2nd vice pres. are nodes below on the next level. This continues down the corporate chain. When the CEO quits, the two vice pres will compete for the root of the tree. This also goes for every other node of the tree.
    Code:
    tree:
                                 y
                             /        \ 
                          r             p
                        /   \         /    \
                     d       f      b      k
                   /   \   
                  a    c
    list:
             y,r,p,d,f,b,k,a,c
    I have always used contiguos lists to implement heaps. This is because you need random access to all parts of the list.

    Here are some functions to Bulid the heap, insert into the heap, and sort the heap.

    Heap Sort is a very good way to implement a priorty queue.

    Code:
    typedef int Position;
    typedef int KeyType;
    
    typedef struct listentry {
      KeyType key;
    } ListEntry;
             
    
    typedef struct list {
            int count;
            ListEntry entry[MAXLIST];
    } List;
    
    
    /* HeapSort: sort contiguous list by the heap sort method.
    Pre:  List has been created and each entry has a key.
    Post: The entries in the list have been rearranged so that the keys
          are in nondecreasing order.
    Uses: BuildHeap, InsertHeap.
    */
    void HeapSort(List *list)
    {
      Position lu;
      ListEntry current;
      BuildHeap(list);
      for(lu  = list->count - 1;lu >= 1; lu--) {
        current = list->entry[lu];
        list->entry[lu] = list->entry[0];
        InsertHeap(current, 0, lu -1, list);
      }
    }
    
    /*InsertHeap: insert an entry into the heap.
      Pre:  The entries of the contiguous list between indices
            low + 1 and high, inclusive, form a heap.  The entry
            in posotion low will be discarded.
      Post: The entry current has bee insertedinto the list and 
            the entries rearranged so that the entries between
            indices laow and high, inclusive, form a heap.
    */
    void InsertHeap(ListEntry current, Position low, Position high, List *list)
    {
      Position large;
      large = 2*low + 1;
      while (large <= high){
        if (large < high && LT(list->entry[large].key, list->entry[large + 1].key))
          large++;
        if (GE(current.key , list->entry[large].key))
          break;
        else {
          list->entry[low] = list->entry[large];
          low = large;
          large = 2*low + 1;
        }
      }
      list->entry[low] = current;
    }
    
    
    void BuildHeap(List *list)
    {
      Position low;
      for(low = list->count/2 - 1;low >= 0;low--)
        InsertHeap(list->entry[low], low, list->count, list);
    }
    Heapsort is better than quicksort, and better than mergesort with contiguous list.
    Last edited by stautze; 04-22-2002 at 01:37 AM.

  3. #3
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    This is Richard Heathfield's implementation of inserting items:
    Code:
    int HeapInsert(HEAP *Heap, 
                   int Tag, 
                   size_t Size, 
                   void *Object, 
                   HEAP_COMPARE Comp)
    {
      int i, j;
    
      int Done = 0;
      int Okay = 1;
    
      void *NewObject = NULL;
    
      assert (Heap != NULL);
    
      NewObject = malloc(Size);
      if(NULL == NewObject)
      {
        Okay = 0;
      }
      else
      {
        memcpy(NewObject, Object, Size);
      }
    
      if(Okay && Heap->Count >= Heap->MaxCount)
      {
        Heap->Heap = realloc(Heap->Heap,
                             2 * Heap->MaxCount *
                                 sizeof *Heap->Heap);
        if(Heap->Heap != NULL)
        {
          Heap->MaxCount *= 2;
        }
        else
        {
          Okay = 0;
          free(NewObject);
        }
      }
    
      if(Okay)
      {
        /* Knuth's Algorithm 5.2.3-16.  Step 1. */
        j = Heap->Count + 1;
    
        while(!Done)
        {
          /* Step 2. */
          i = j / 2;
    
          /* Step 3. */
          if (i == 0 || (*Comp)(Heap->Heap[i - 1].Object,
                                Heap->Heap[i - 1].Tag,
                                Object,
                                Tag) <= 0)
          {
            Heap->Heap[j - 1].Tag = Tag;
            Heap->Heap[j - 1].Size = Size;
            Heap->Heap[j - 1].Object = NewObject;
            Heap->Count++;
            Done = 1;
          }
          else
          {
            /* Step 4. */
            Heap->Heap[j - 1] = Heap->Heap[i - 1];
            j = i;
          }
        }
      }
    
      return Okay;
    }
    But i don't understand how it will insert items in order.
    If the object is bigger than the half item, why is then the object assigned to the second item of the heap. And if the object is smaller than the half item, why does it half again.

  4. #4
    Registered User stautze's Avatar
    Join Date
    Apr 2002
    Posts
    195
    That is the thing about the heap. It does get things in order, it only guarantees that the parent node has greater priority than the children. Thus the root of the heap always has the highest priority.

  5. #5
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    Ok, but is a heap a list or a tree? If it's a list, why mention parent nodes? No such thing in lists.

  6. #6
    Registered User stautze's Avatar
    Join Date
    Apr 2002
    Posts
    195
    It is a list, but it is much easier to visualize as a tree since there is no ordering of the items in the list except for that the first item in the list has the highest priority.

  7. #7
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    Thnx.

    I am really confused with the dequeue algorithm. Is there any online applets or diagrams or flow charts that can help visualize the proceess?

  8. #8
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Warning this is long and probably has some mistakes.


    A heap is a priority queue. What you want is a data structure
    so that supports removing the highest object first and inserting
    into the priority queue. Now as others have said, the
    most typical way to do this is with arrays. But it is
    worth noting that there are other
    data structures such as leftest queues using trees.

    Once we have an implementation of a priority queue all that we need to do is to insert every object in the array were sorting. Then we keep on removing the object with highest priority. The trickis that there's a faster way to transform an array
    into heap but it's probably best to understand heap insertion and
    removal first.

    So heap sort is not hard to understand it's the concrete heap implementation.

    What we want to do is to set up our array so that it is a complete binary tree. We let A[1] is the root, A[0] is unused as
    it makes the code easier to understand/faster. The root we define as having the highest priorty. Then given a index i,
    A[i * 2] is its left child, A[i*2 + 1] is it's right child, A[i / 2] is its parent. All this is done with integer division.

    Once this is done we can
    map any operation we do with our trees into the array.
    For the operation of removing the "min" element or the
    element with highest priority in a heap such as. What
    we want to do is this:
    Code:
                                 1
                             /        \ 
                          3             4
                        /   \         /    \
                     8      10   11     5
                   /   \   
                  9    12
    Conceptionally we want to remove 1 and keep the
    heap order property and complete tree property.  A complete
    tree is a tree such as 
                                 1
                             /        \ 
                          3             4
                        /   \         /    \
                     8      10   11     5
                   /   \   
                  9    12
                                 1
                             /        \ 
                          3             4
                        /   \         /    \
                     8      10   11     5
                   /      
                  9    
                                 1
                             /        \ 
                          3             4
                        /   \         /    
                     8      10   11    
    
                                 1
                             /        \ 
                          3             4
                        /   \         /    \
                     8      10   11     5
    
    This one is *not* complete.
                                 1
                             /        \ 
                          3            4
                        /   \            \
                     8      10           5
    
    From pictures it easy to tell if a tree is complete
    or not.
                          
    Now since the tree is going to be one less after
    removal we know that 12 must be moved to somewhere.  
    What we can do is form a "bubble" B, sort of like bubble sort where 1 used to be.  This is really is just a placeholder to make it easier to understand.  Since we are going to move 12 
    we let tmp = 12 and remove 12 also.
    
                                 B
                             /        \ 
                          3             4
                        /   \         /    \
                     8      10   11     5
                   /   
                  9   
    Now we want to move that bubble down the tree and eventually
    replace it with 12.  To do this swap 3 and B. 
                                 3
                             /        \ 
                          B             4
                        /   \         /    \
                     8      10   11     5
                   /      
                  9   
    swap 8 and B
                                 3
                             /        \ 
                          8             4
                        /   \         /    \
                     B      10   11     5
                   /      
                  9   
    swap 9 and B
                                 3
                             /        \ 
                          8             4
                        /   \         /    \
                     9      10   11     5
                   /      
                  B   
    Then since were at the end replace B with 12.
    
                                 3
                             /        \ 
                          8             4
                        /   \         /    \
                     9      10   11     5
                   /      
                 12
    
    Now let's remove 3.
    tmp = 12.
                                 B              
                             /        \ 
                          8             4
                        /   \         /    \
                     9      10   11     5
    Swapping B and 4      
                                 4              
                             /        \ 
                          8             B
                        /   \         /    \
                     9      10   11     5
    Swapping 5 and B
                                 4              
                             /        \ 
                          8             5
                        /   \         /    \
                     9      10   11     B
    and swapping B and 12
                                 4              
                             /        \ 
                          8             5
                        /   \         /    \
                     9      10   11     12
    Let's look at a more interesting example
                                 4              
                             /        \ 
                          8             5
                        /   \         /    \
                     9      10   11     6
    We want to remove 4.
    We let tmp = 6.
                                 B
                             /        \ 
                          8             5
                        /   \         /    
                     9      10   11    
    Swapping 5 and B
                                  5
                             /        \ 
                          8             B
                        /   \         /    
                     9      10   11   
    But since 11 > 6 it is safe to swap B and 6 and so
    we have
                                  5
                             /        \ 
                          8             6
                        /   \         /    
                     9      10   11   
    
    Now you probably see it will be faster not to swap values
    and to just move B down the tree.  
    
    
    Now say we want to insert 6 in
                                 1
                             /        \ 
                          3             4
                        /   \         /    \
                     8      10   11     5
                   /   \   
                  9    12
    For a first step we know to make the tree complete
    we will need to make 10 have a left child.  Thus we
    can start with
                                  1
                             /         \ 
                          3              4
                        /    \          /    \
                     8        10   11     5
                   /   \      /
                  9    12 B
    Now we want to move the bubble B up until we can
    insert 6.  Since 6 < 10
                                  1
                             /         \ 
                          3              4
                        /    \          /    \
                     8        B   11     5
                   /   \      /
                  9    12 10
    But as 6 > 3.
                                  1
                             /         \ 
                          3              4
                        /    \          /    \
                     8        6   11     5
                   /   \      /
                  9    12 10
    
    Now let's look at what happens when we have
    an array A and we want to transform that array into a heap.
    First we have a random tree such as 
                                  6
                             /         \ 
                          8              4
                        /    \          /    
                     1        5     7      
    What we want to do is push 7 parent as far down
    the tree as possible.  Then 5's parent as far down
    the tree as possible, then 4's parent as far down the
    tree as possible.
    Since 4 < 7
                                  6
                             /         \ 
                          8              4
                        /    \          /    
                     1        5     7      
    Since 8 > 1
                                  6
                             /         \ 
                          1              4
                        /    \          /    
                     8        5     7      
    Since 1 < 6
                                  1
                             /         \ 
                          6              4
                        /    \          /    
                     8        5     7
    I'm not going to get into details but it can be shown that
    this proccess is O(log n).

  9. #9
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    I guess you will have to draw the trees out on paper .

  10. #10
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    Nick,

    Thnx very much for detailed explanation!

  11. #11
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    When you create a heap from
    a binary array it's O(n) not O(log n).
    That was the general idea of heap sort
    but there are ways to make it more efficient
    by not using an extra array. And of course
    you call the array implementation a binary
    heap.

  12. #12
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    My book uses linked lists.

  13. #13
    Registered User stautze's Avatar
    Join Date
    Apr 2002
    Posts
    195
    Linked list could be better dependending on what size the nodes are, how big the list is, and how often you will be resorting. It is really up to the programmer to balance speed and resources.

  14. #14
    The Artful Lurker Deckard's Avatar
    Join Date
    Jan 2002
    Posts
    633
    You guys need this.
    Jason Deckard

  15. #15
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    typedef struct listentry {
    KeyType key;
    } ListEntry;


    typedef struct list {
    int count;
    ListEntry entry[MAXLIST];
    } List;
    This is an array. Heathfield uses a dynamic array.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Buffers , heaps , stacks ...
    By BlaX in forum Tech Board
    Replies: 9
    Last Post: 02-17-2009, 03:09 PM
  2. Buffers , heaps , stacks ...
    By BlaX in forum C Programming
    Replies: 1
    Last Post: 02-17-2009, 01:11 PM
  3. Heaps!
    By Leojeen in forum C Programming
    Replies: 18
    Last Post: 11-26-2008, 01:31 AM
  4. Help With Heaps
    By Dangerous Dave in forum C++ Programming
    Replies: 8
    Last Post: 11-23-2004, 08:47 AM
  5. FAQ heaps
    By face_master in forum FAQ Board
    Replies: 2
    Last Post: 10-06-2001, 11:21 AM