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.