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

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.

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.

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.

Ok, but is a heap a list or a tree? If it's a list, why mention parent nodes? No such thing in lists.

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.

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?

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).

I guess you will have to draw the trees out on paper :(.

Nick,

Thnx very much for detailed explanation!

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.

My book uses linked lists.

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.

You guys need this.

Quote:

---

typedef struct listentry {
KeyType key;
} ListEntry;


typedef struct list {
int count;
ListEntry entry[MAXLIST];
} List;

---

This is an array. Heathfield uses a dynamic array.