Lesson 11. Heaps
Note: To get it to fit on the screen, I had to make the code for heapify really small. I apologize for the inconvenience.
Okay, as far as trees go we’re almost out of the woods (please excuse the lame pun). There is one more type of tree you will be learning about and that is heaps. They will be useful in sorting, which will be covered in the next lesson, and heaps will be the return of the array tree I told you about in the introduction to trees and then totally ditched.
Please note that since the main use of heaps that we are considering is the heapsort algorithm, in my implementation of heaps, heaps do not get their own class. Instead, their functions are standalone functions that work on arrays (they can work on regular arrays, but in my implementation we will use dynamic arrays). Moreover, heaps break the traditional rule of arrays by using 1 as their first space instead of 0. (They can be programmed to use zero-indexing like other arrays, but one-indexing makes them easier to program).
Anyway, a let’s get started already! A heap is a binary tree in which:
1. The tree is complete, meaning that before starting a new level on the tree, the current bottom level must be filled completely. (The order of filling each level of this tree will be from the leftmost node of each level of the tree to the rightmost node.)
2. The tree has the heap property, which means that:
·
If the tree is a maxheap, every node has to have data with a value greater than or equal to that of its children.
· If the tree is a minheap, every node has to have data with a value less than or equal to that of its children.
For all examples in this tutorial, we will be dealing with maxheaps. However, it only takes a few modifications of the code you are given to make a minheap out of an array.
This is a maxheap. Please note while this heap is a binary tree, but it is NOT a binary search tree.
To maintain the heap property, each node must be in contact with both its parent node (unless it is the root node) and its child or children (unless it is a leaf node).
There are two ways to do this:
1. Make the heap into a doubly-linked tree where every node has pointers to its parent and children, and suffer through the many segfaults that probably will come out of making it.
2. Use a dynamic array, which inherently comes with the INDEXING PROPERTY, and take advantage of the indexing property to gain access to each node’s parent and children through ONE-LINE functions!
Which one sounds good to you? I don’t know about you, but as much as I love working in Halligan, I want to make my code fast and efficient to write so I don’t have to have a sleepover in there. Also, in addition to being easier to write, array-based heaps are also more efficient to execute. To access one of the bottom nodes in this kind of structure, it would take a pretty good O(log2n) runtime, but in an array, the inherent indexing property gives us the ability to access ANY node in one easy step, blazing across the tree in a super fast O(1)!
Also remember that in an array tree, to make the math easier we have indexing starting at 1; by doing that, we just made it so that:
A node heap[x]’s left child is heap[2 * x], unless we are at a leaf node, which has no children.
A node heap[x]’s right child is heap[2 * x + 1], unless we are at a node that has no right child.
A node heap[x]’s parent is heap[x/2] (remember that C++ uses integer division), unless we are at node 1 in which case we are at the root node, which has no parent.
Because of this, we can get the INDICES of a node’s parent and children with these simple one-line functions.
int parent(int nodeIndex)
{
return (nodeIndex / 2);
}
int leftChild(int nodeIndex)
{
return (nodeIndex * 2);
}
int rightChild(int nodeIndex)
{
return (nodeIndex * 2 + 1);
}
Also, since this is a dynamic array we’re working with, this means that we will need variables to keep track of the heap’s size and maximum capacity (called size and maxSize) and we will also need a function to expand it. This function is called addLevel and it’s essentially the same as the doubleSize functions we have seen in dynamic arrays before, with a few minor changes:
void addLevel(int*& heap, int &size, int &maxSize)//1
{
int* temp = new int[(size+1)*2];//2
for(int i = 1; i <= size; i++)//3
temp[i] = heap[i];
delete[] heap;
heap = temp;
maxSize = maxSize * 2 + 1;//4
}
1. Since the heap is not a member of any class, to permanently double its size we need to pass it as a parameter by reference. In addition, size and maxSize are two variables that are independent of heap and not part of any class, so they also need to be passed by referreence to be changed outside of the function.
2. When we create the temp heap, we need to remember that heaps use one-indexing instead of zero-indexing. This means that the original size of the array was actually one more than the size of the heap (we do not use heap[0]). Also, the size of each level is one plus the size of all previous levels added together, so that means that to increment the heap by one level, we need to double the size of the ARRAY and NOT THE HEAP.
3. Another result of this one-indexing is that in order to copy the heap over to the new larger heap, we start at heap[1] and end at heap[size], rather than starting at heap[0] and ending at heap[size-1].
4. Moreover, this also means that since it is the array’s size that we are doubling, the maximum capacity of the HEAP is not doubled, it is doubled and then incremented by one.
As for the size variables in a heap, when a heap is first created, because we want each call of addLevel to expand the HEAP by one level, the initial size of a HEAP should be 0, the initial size of the ARRAY should be a power of 2 (doubles with each call of addLevel), and the initial maxSize of the heap should be that power of 2 minus one. In other words, here is what the initial declaration of the heap should look like:
int* heap = new int[8];
int size = 0;
int maxSize = 7;
This is what a call to addLevel looks like in the form of the heap and the array.
Also, since we are keeping track of the heap’s size, the isEmpty function is just a simple one-liner:
bool isEmpty(int size)
{
return (size == 0);
}
The next function, getLargest, is another easy one-line function. It just retrieves the largest item in the array, and since in a maxheap that item is always at position 1, that means the function is as easy as…
//Invariant: getLargest is not to be used on an empty heap.
int getLargest(int* heap)
{
return heap[1];
}
So, now we’ve seen the one-liners. Here’s where it starts to get interesting. We now have to deal with the insert and remove functions.
In the insert function, we start by inserting an item at the last position of the heap. However, unless we are inserting the very smallest item into the heap, we will need to swap some of the elements of the heap to maintain the heap property.
//Invariant: heapInsert is only to be used when the array has the heap property.
void insert(int*& heap, int &size, int &maxSize, int x)//1
{
size++;//2
heap[size] = x;
if(size == maxSize)
addLevel(heap, size, maxSize);
int xLoc = size;//3
while(x > heap[parent(xLoc)] && xLoc > 1)//4
{
int temp = heap[xLoc];
heap[xLoc] = heap[parent(xLoc)];
heap[parent(xLoc)] = temp;
xLoc = parent(xLoc);//5
}
}
1. Size is passed by reference since size is changed when insert is called. In addition, since there is the possibility that addLevel is called, which expands maxSize, maxSize is also passed into the function by reference.
2. Size is incremented, and if maxSize has been reached, addLevel is called.
3. xLoc is created to keep track of the position of the item carrying the int just inserted.
4. In each iteration of the loop, if the item at xLoc is less than its parent, then it is swapped with its parent.
5. After this, xLoc is moved to the parent of the item at index xLoc so that we are still having xLoc keep track of the item we inserted.
By the way, the term for swapping upwards or downwards to get an item to its correct position is called percolating up/down.
The one other function that we need to make is removeMax, which removes the largest (first) item.
Since the first item has no parent, which child do we put as the new first item? Well, why not put the last item there so we don’t have to re-shape the whole tree just to find a new first item?
Here’s the function.
//Invariant: removeMax will not be used on empty heaps.
int removeMax(int* heap, int &size)//1
{
int max = heap[1];
if(size == 1)//2
size = 0;
else
{
heap[1] = heap[size];//3
size--;
int x = heap[1];
int xLoc = 1;//4
bool inPosition = false;
while(!inPosition)
{
if(leftChild(xLoc) == size)//5
{
if(heap[leftChild(xLoc)] > x)//6
{
heap[xLoc] = heap[size];
heap[size] = x;
}
inPosition = true;
}
else if(leftChild(xLoc) > size)//7
inPosition = true;
else//8
{
if(heap[leftChild(xLoc)] > x || heap[rightChild(xLoc)] > x)
{
int newXLoc;
if(heap[leftChild(xLoc)] > heap[rightChild(xLoc)])
newXLoc = leftChild(xLoc);
else
newXLoc = rightChild(xLoc);
heap[xLoc] = heap[newXLoc];
heap[newXLoc] = x;
xLoc = newXLoc;
}
else
inPosition = true;
}
}
}
return max;
}
1. Once again, we are passing size by reference since size changes during the function call.
2. If we are removing the only item in the array, we just need to set size to zero and then return
the one item we just removed.
3. If we are removing from an array with more than one item, the first step is to set the first item of the heap equal to the last item of the heap. After this, size is decremented by 1, so the original last item of the heap is still in the array but no longer in an element of the array that is in the heap.
4. We set xLoc to 1 to keep track of the position of the number we just moved to position 1. We use inPosition to keep track of whether or not the heap property has been restored (when the item that was moved to position 1 reaches a position at which it is smaller than its parent and larger than any children it has, the heap property is restored and inPosition is set to true).
5. If the left child of the item at position xLoc is equal to size, then that means that the current node’s left child is the last element of the heap and the current node does not have a right child.
6. Because of this, all we need to do in that case is check if element xLoc is greater than its child. If it is not, we will swap them, and the heap property is restored, so inPosition is set to true. If element xLoc is greater than its child, then nothing is changed and inPosition is set to true.
7. If xLoc * 2 is greater than size, then that means that xLoc is now on the last level of the tree, so the heap property is restored since the item at position xLoc does not have any children.
8. If the left child of the item at position xLoc is less than size, then the item at position xLoc must have two children. If neither child is bigger than the item at position xLoc, then the heap property has been restored so inPosition is set to true. Otherwise, we then swap the item at position xLoc with the bigger of its two children and then set xLoc equal to the index of that child.
As you can see, this algorithm for removing the largest item in the heap involves percolating the new top item down to its proper position.
Notice that to remove the maximum item it takes at most three swaps. That shows that each removeMax has a runtime of O(log2n). Remember that. It will be important in the next lesson.
Finally, the last function I would like to show you is heapify. For this function, we take an array representing a complete tree and turn it into a heap by giving it the heap property.
//Invariant: Heapify will not be used on an empty array.
void heapify(int* heap, int size)
{
if(size > 1)//1
{
for(int i = size/2; i >= 1; i--)//2
{
if(rightChild(i) <= size)//3
{
if(heap[i] < heap[leftChild(i)] || heap[i] < heap[rightChild(i)])//4
{
int current = i;
bool inPosition = false;
while(!inPosition)
{
int temp = heap[current];
if(rightChild(current) <= size)
{
if(heap[current] < heap[leftChild(current)] || heap[current] < heap[rightChild(current)])
{
if(heap[leftChild(current)] > heap[rightChild(current)])
{
heap[current] = heap[leftChild(current)];
heap[leftChild(current)] = temp;
current = leftChild(current);
}
else
{
heap[current] = heap[rightChild(current)];
heap[rightChild(current)] = temp;
current = rightChild(current);
}
if(leftChild(current) > size)//5
{
inPosition = true;
}
}
else
{
inPosition = true;
}
}
else//6
{
if(heap[current] < heap[leftChild(current)])
{
heap[current] = heap[leftChild(current)];
heap[leftChild(current)] = temp;
}
inPosition = true;
}
}
}
}
else//7
{
if(heap[i] < heap[leftChild(i)])
{
int temp = heap[i];
heap[i] = heap[leftChild(i)];
heap[leftChild(i)] = temp;
}
}
}
}
}
1. If size is equal to 1, then the array already has the heap property, so we only need to heapify the array if there is more than one element in the array.
2. Heapifying involves repeatedly percolating items down in every element that has at least one child. Because of this, we start the heapify process on the node at a position of size/2 (with integer division), which is the last node in the heap to have a child node.
3. This if statement checks if the node being checked has a right child in addition to its left child.
4. If the node being checked does have a right child, then for each item i, if the element of the array at position i is less than either of its two children, then the element at position i is swapped with its larger child and percolated down in a loop until it is either at a leaf node or larger than its child or children. If the element is larger than both of its children, that means that the item is in its correct position.
5. If the left child of the current node has an index greater than size, that means that the current node is now at a leaf node, which means that the current node is in its correct position.
6. If the current node does not have a right child, then its only (left) child has to be at a leaf. That means that if the current node has a value greater than that of its child it is already in the correct position. Otherwise, the current node is swapped with its child, and since it is now on a leaf node that means that it is now in its correct position.
7. Essentially the same as 6, except this is for if the node at position i only had a left child to begin with.
Overall, we loop through half of the items in the list O(n/2) and each percolation takes at most three steps O(log2n). This means that heapify has an efficient runtime of O(nlog2n).
So… we have a function that can turn an array into a heap, and once we make a heap, we can remove the largest item from the heap one by one. Are you thinking what I’m thinking? If so, check out the next lesson, which will be on fast sorting algorithms.
No comments :
Post a Comment