COMP1927 - Heaps

Heaps are a data structure in C.

The Two Properties That Define a Heap

Heap Invariant

The Heap Invariant means simply that a child is always less than its parents.

Completeness

Completeness means that the heaps is always filled in left to right. It means that insertion is a very simple initial step; find the last filled in node, and fill in the one after that.

This means that there will always be log(n) levels, as each level is filled incrementally.

Differences Between Heaps and BSTs

Binary Search Trees are ordered left-to-right; new elements are inserted as leaf nodes, and when read in an infix style the tree is ordered left-to-right.

Heaps are ordered top-to-bottom; new elements are inserted at the end and then bubbled up, so as to ensure that every branch is ordered from top to bottom.

Implementation

It's possible to implement a heap with an array or a linked list structure, however heaps are commonly implemented with an array because of the neatness of the completeness property.

Insertion

Inserting into a heap is simple; place the new item in the last position and then bubble it up to the correct position, where it is greater than its children and less than its parent.

// Last must be updated outside of insert
void insert (int pqueue[], int data, int last) {
   // Insert the data into the next position
   // As per the completeness principle
   pqueue[last+1] = data;
 
   // Start the bubbling up process 
   // Temp is used to store the swapping of the parent/child when bubbling
   int temp;
 
   last = last + 1;
   int startIndex = last;
   int parentIndex = (startIndex / 2);
 
   // While it's not following the heap invariant (ordered)
   // And we haven't reached the top of the heap
   // We compare the node with its parent
   // And swap until it's in the right place
   while ((parentIndex >= START) && 
            (pqueue[parentIndex] < pqueue[startIndex])) {
      temp = pqueue[parentIndex];
      pqueue[parentIndex] = pqueue[startIndex];
      pqueue[startIndex] = temp;
      startIndex = parentIndex;
      parentIndex = (startIndex / 2);
   }
 
}

Deletion

Deleting from a heap is also quite simple; swap the first item with last item and then bubble the new one down into place.

// Last must be updated outside of delete
int delete (int pqueue[], int last) {
   // Store the top element
   int popped = pqueue[START];
 
   // Move the last element up to the top
   pqueue[START] = pqueue[last];
 
   // Reset last element to 0
   pqueue[last] = 0;
 
   // Start the bubbling down process
   last = last-1;
   int startIndex = START;   
 
   // '+ 1 - START' generalises the heap to either a 0 or 1 based array
   int childIndex1 = (startIndex * 2) + 1 - START;      
   int childIndex2 = (startIndex * 2) + 2 - START;
 
   int biggestChild;      
   // While it's not following the heap invariant (ordered)
   // And we haven't reached the bottom of the heap
   // We compare the node with its two children, 
   // And then swap with the biggest until it's in the right place
   while ((startIndex <= (last/2)) && 
            (pqueue[startIndex] < 
             max(pqueue[childIndex1], pqueue[childIndex2]))) {
      biggestChild = maxAddress(pqueue, childIndex1, childIndex2);
      temp = pqueue[startIndex];
      pqueue[startIndex] = pqueue[biggestChild];
      pqueue[biggestChild] = temp;
      startIndex = biggestChild;
      childIndex1 = (startIndex * 2) + 1 - START;
      childIndex2 = (startIndex * 2) + 2 - START;
   }
 
   // Return the top element
   return popped;   
 
}

Printing

Printing a heap in a straight list format is very simple (essentially just a for loop), but printing it out in a graphical representation requires determining the spacing, which is more fiddly.

// Print the list visually in the heap structure
/* E.g.
    8
  5   3
 4 1 2 2
*/
void print (int pqueue[], int last) {
 
   // New line is needed after every  '2^n - 1'th element
   // After every new line 
   // Divide the number of spaces between each element by 2
   // The initial number of spaces is 2^numLines
   // Also known as last rounded up and divided by 2
 
   // %*c prints out (the argument before %c) number of spaces
   // Followed by the %c
   // So my code prints numSpaces without needing a loop to do it
 
   int numSpaces = exponential(2,(calculateNumLevels(last)));
 
   int i;
   for (i = START; i <= last; i++) {
      printf ("%*c%d%*c", numSpaces-1, ' ', pqueue[i], numSpaces, ' ');
      if (lineEnd(i)) {
         numSpaces /= 2;
         printf ("\n"); 
      }
   }
 
   // If the last line didn't end on a newline end
   // We need to print that \n now
   if (!lineEnd(i-1)) {
      printf ("\n");
   }  
 
}

Print Helper Functions

// Print helper function
// Calculate the number of levels in the standard heap format
int calculateNumLevels (int n) {
 
   int i;
   for (i = 0; n >= 1; i++) {
      n /= 2;
   }  
 
   return i;
 
}
 
// Print helper function
// A number is a line end if it is one less than a power of two
int lineEnd (int n) {
 
   // Increment n by one and then test if it is a power of two
   n += 1;
 
   int result = TRUE;
 
   while ((n > 1) && (result)) {
      if ((n % 2) == 0) {
         n /= 2;
      } else {
         result = FALSE;
      }
   }
 
   return result;
 
}
 
// Takes in a base and exponent and returns base^exponent
int exponential(int base, int exponent) {
 
   int result = 1;
 
   int i;
   for (i = 0; i < exponent; i++) {
      result *= base;
   }
 
   return result;
 
}

Heap Sort

Heap sort is a very simple sort which involves putting all the elements into a heap and then 'deleting' the first element to become the last, leaving you with a sorted list.