heap.c

Go to the documentation of this file.

/** \file heap.c

\brief Heap code

Array starts at 
zero, so left and right children are at (2*index + 1) 
and ( 2 * index + 2 ).

******************************************************************************/

#include "heap.h"

/**AutomaticStart*************************************************************/

/**AutomaticEnd***************************************************************/


/**
  * \brief  Return index of left child
  * 
  */

static inline int
leftChild (int index)
{
  return ((2 * index) + 1);
}


/**
  * \brief  Return index of right child
  * 
  */

static inline int
rightChild (int index)
{
  return ((2 * index) + 2);
}


/**
  * \brief  Return index of parent
  * 
  */

static inline int
getParent (int index)
{
  if (index == 0)
    {
      printf ("root has no parent!\n");
      assert (0);
    }
  return ((index % 2) == 1) ? (index / 2) : ((index - 1) / 2);
}


/**
  * \brief  Create a heap with N entries
  * 
  */

Heap_t *
Heap_InitN (int (*less) (char *, char *), int N)
{
  assert (N >= 0);
  Heap_t *result = (Heap_t *) malloc (sizeof (Heap_t));
  result->less = less;

  result->entryArray = array_alloc (char *, N);
  return result;
}


/**
  * \brief  Create a heap with 0 entries
  */

Heap_t *
Heap_Init (int (*less) (char *, char *))
{
  return Heap_InitN (less, 0);
}


/**
  * \brief  Insert an entry into a heap
  */

void
Heap_Insert (Heap_t * aHeap, char *entry)
{
  array_insert_last (char *, aHeap->entryArray, entry);

  unsigned int index = array_n (aHeap->entryArray) - 1; // this is the index of what we just inserted
  char *current = entry;
  char *parent = NIL (char);
  while (1)
    {
      if (index == 0)
    {
      return;       // it's at the top of the heap
    }
      parent = array_fetch (char *, aHeap->entryArray, getParent (index));
      int currIsLessThanParent = aHeap->less (current, parent);
      if (currIsLessThanParent)
    {
      return;       // heap invariant is satisfied
    }
      else
    {
      // perform swap - current goes to getParent( index ),
      // parent goes to index
      // index becomes its parent
      array_insert (char *, aHeap->entryArray, getParent (index),
            current);
      array_insert (char *, aHeap->entryArray, index, parent);
      index = getParent (index);
    }
    }
  assert (0);
}


/**
  * \brief  Returns the number of elements in the heap
  */

int
Heap_Size (Heap_t * aHeap)
{
  return array_n (aHeap->entryArray);
}


/**
  * \brief  Return the max element of the heap; does not change heap
  */

char *
Heap_ReadMax (Heap_t * aHeap)
{
  array_t *entryArray = aHeap->entryArray;
  assert (array_n (entryArray) > 0);
  char *result = array_fetch (char *, entryArray, 0);

  return result;
}


/**
  * \brief  Take a heap which satisfies the heap property everywhere but
  * possibly the root, and make it into a heap
  * 
  */

void
Heap_Heapify (Heap_t * aHeap)
{
  array_t *entryArray = aHeap->entryArray;
  int (*less) (char *, char *) = aHeap->less;

  int numEntries = array_n (entryArray);
  if (numEntries == 0)
    {
      return;
    }
  unsigned int rootIndex = 0;
  char *root = array_fetch (char *, entryArray, rootIndex);
  char *child0, *child1;
  while (1)
    {
      if (leftChild (rootIndex) < numEntries)
    {
      child0 = array_fetch (char *, entryArray, leftChild (rootIndex));
    }
      else
    {
      child0 = NIL (char);
    }
      if (rightChild (rootIndex) < numEntries)
    {
      child1 = array_fetch (char *, entryArray, rightChild (rootIndex));
    }
      else
    {
      child1 = NIL (char);
    }
      if (child0 == NIL (char))
    {
      return;       // nothing to swap with
    }
      if (child1 == NIL (char))
    {
      // have only a left child
      if (less (root, child0))
        {
          array_insert (char *, entryArray, rootIndex, child0);
          array_insert (char *, entryArray, leftChild (rootIndex), root);
        }
      return;       // only one child means we're done
    }
      if (!less (root, child0) && !less (root, child1))
    {
      // root is bigger than both children, so we're done
      return;
    }
      if (less (child0, child1))
    {
      // child0 is less than child1 so swap with child1
      array_insert (char *, entryArray, rootIndex, child1);
      array_insert (char *, entryArray, rightChild (rootIndex), root);
      rootIndex = rightChild (rootIndex);
    }
      else
    {
      // child1 is less than child0, so swap with child0
      array_insert (char *, entryArray, rootIndex, child0);
      array_insert (char *, entryArray, leftChild (rootIndex), root);
      rootIndex = leftChild (rootIndex);
    }
    }
  assert (0);
}

/**
  * \brief  Code to test the heap package
  */

int
Heap_Test ()
{
  Heap_t *aHeap = Heap_Init ( ( int (*)(char*, char*) ) strcmp);

  Heap_Insert (aHeap, "foo");
  Heap_Insert (aHeap, "bar");
  Heap_Insert (aHeap, "a");
  Heap_Insert (aHeap, "123");

  printf ("%s\n", Heap_ReadMax (aHeap));
  Heap_Insert (aHeap, "goo");
  Heap_Insert (aHeap, "zzz");
  Heap_Insert (aHeap, "bar");
  printf ("%s\n", Heap_ReadMax (aHeap));

  return 0;
}