- Introduction to Heaps
- The Heap Class
- Heap Implementation
- Testing the Heap Class
- More Testing of Heap
- Extending the Heap Class
- Add a second constructor function to "heap.h" that takes an integer parameter "MaxSize".
- Change the private "heap" variable into an integer pointer.
- Implement the second constructor function in "heap.cpp" using "new" to allocate space for the heap data.
- Add code to the destructor function to release memory using "delete" when the object is destroyed.
- Modify your main program to create the heap of size N after reading this value from the user.
- Retest your new and improved program with a variety of N values.
- Creating a Min-Heap from a Max-Heap
- Submit Work

This laboratory assignment focuses on the heap data structure. Heaps are often used to implement priority queues and to implement an O(NlogN) sorting algorithm named "heap_sort". The remainder of the lab goes into the implementation and use of this abstract data type in more detail.

A heap is a special type of binary tree with two essential
properties: 1) the values in each node are **larger** than all
of their children nodes, and 2) the binary tree is **complete**,
all of the levels in the tree are full except possibly the lowest
level of the tree, which is filled in from left to right.

What is a heap good for? It is a very good data structure for storing/retrieving N data values, where the largest value is always on the root of the tree. Since a binary tree is used, the cost of each insertion or deletion is O(logN) steps, which is far faster than we could expect using an unsorted or sorted array or linked list.

By restricting a heap to be a complete binary tree, it turns out that we can store the values in a heap in an array instead of using nodes with left, right, parent pointers. The trick is to store the root at location 1. For all nodes in the tree, we store the left child of node K in location 2K, and the right child of node K in location 2K+1. The result is that as we fill the array from positions 1-N by traversing the heap from top-bottom, and left-right. This is illustrated below.

Consider the following C++ declaration of the Heap class. You will see that the class has five public operations: Insert, Remove, IsFull, IsEmpty, and Print. You will also see that the private data for the heap is stored in a fixed size array of integers called "heap". The number of values stored in this array is in the private integer "Count".

//------------------------------------------------------------ // Purpose: Header file for the Heap class. // Author: John Gauch //------------------------------------------------------------ #include < iostream > using namespace std; //------------------------------------------------------------ // The Heap class definition for a heap of integers //------------------------------------------------------------ #define MAX_HEAP_SIZE 20 class Heap { public: // Constructor functions Heap(); ~Heap(); // General heap operation bool Insert(int num); bool Remove(int &num); bool IsEmpty(); bool IsFull(); void Print(); private: int Count; int heap[MAX_HEAP_SIZE+1]; };

Consider the implementation of the Heap class below. The "Insert" method takes an integer, and stores it at the next available position in the array. In the tree, this is just to the right of the last node on the bottom level. Then the new value is shuffled up the tree to ensure that all nodes are greater than all of their children nodes.

The "Remove" command returns the value in position 1 in the array, and then moves the value from the last position in the array into position 1. Then it shuffles values down the tree to ensure that all nodes satisfy the heap properties. This process is more complex than "Insert" but it still takes O(logN) steps in the worst case.

//------------------------------------------------------------ // Purpose: Implementation of integer Heap class. // Author: John Gauch //------------------------------------------------------------ #include "heap.h" //------------------------------------------------------------ // Constructor function. //------------------------------------------------------------ Heap::Heap() { Count = 0; for (int index = 0; index < MAX_HEAP_SIZE; index++) heap[index] = -1; } //------------------------------------------------------------ // Destructor function. //------------------------------------------------------------ Heap::~Heap() { } //------------------------------------------------------------ // Insert an element into the heap. //------------------------------------------------------------ bool Heap::Insert(int num) { // Check for full heap if (IsFull()) return false; // Shuffle data up the heap Count++; int child = Count; int parent = child / 2; while ((child > 1) && (heap[parent] < num)) { heap[child] = heap[parent]; child = parent; parent = child / 2; } // Insert new entry in heap heap[child] = num; return true; } //------------------------------------------------------------ // Remove an element from the heap. //------------------------------------------------------------ bool Heap::Remove(int &num) { // Check for empty heap if (IsEmpty()) return false; // Save top of heap num = heap[1]; // Swap last value into root position heap[1] = heap[Count]; heap[Count] = -1; Count--; // Shuffle data down the heap int parent = 1; int largest = 0; while (parent != largest) { // Check left node largest = parent; int left = parent * 2; if ((left <= Count) && (heap[left] > heap[largest])) largest = left; // Check right node int right = left + 1; if ((right <= Count) && (heap[right] > heap[largest])) largest = right; // Swap data values if needed if (parent != largest) { int temp = heap[parent]; heap[parent] = heap[largest]; heap[largest] = temp; parent = largest; largest = 0; } } return true; } //------------------------------------------------------------ // Print the contents of the heap. //------------------------------------------------------------ void Heap::Print() { for (int index = 1; index <= Count; index++) cout << heap[index] << " "; cout << endl; } //------------------------------------------------------------ // Check if the heap is empty //------------------------------------------------------------ bool Heap::IsEmpty() { return Count == 0; } //------------------------------------------------------------ // Check if the heap is full //------------------------------------------------------------ bool Heap::IsFull() { return (Count == MAX_HEAP_SIZE); } //----------------------------------------------------------- // Main program. //----------------------------------------------------------- int main() { // ADD HERE }

Copy and paste the class declaration into a file called "heap.h" and the class implementation into a file called "heap.cpp". When you compile and run this in NetBeans, it should do nothing because the main function is empty.

Now extend the main function to create a Heap object called "heap" and call the "Insert" method to add the six values 3 1 4 1 5 9 into the heap. Call the "Print" method after each insertion to see what the heap looks like.

Finally, add a loop to the main function that calls "Remove" over and over again until the method "IsEmpty" returns true. Each time through the loop, print out the value that was removed, and call "Print" to show what the heap looks like.

Cut and paste your new main function below:

Cut and paste your new program output below:

In order to do more extensive testing, modify your main function to prompt user for an integer N, and then replace your insertion code above with a loop that calls "Insert" with N random values between [0..N-1]. You can base this code on your BinaryTree code from the previous lab. You do not need to modify your "Remove" loop.

Test your new program with N=15, N=20 and N=25. What did you see? Take a look at "heap.h" and "heap.cpp" and see if you can figure out what the problem is. It should be a one line fix to make the program work for N=25.

Cut and paste your new program output below:

It is inconvenient to recompile the Heap class every time we want to increase the size of the heap. To avoid this problem, you are going to convert the fixed size "heap" array into a dynamically allocated array.

Cut and paste your new constructor/destructor functions below.

As you noticed, the Heap class always puts the largest
value at the root of the tree. This form of heap is often
called a "max-heap". There are many applications where
we want to get the **smallest** value from a collection.
This type of heap is called a "min-heap".

There are two ways to quickly convert a "max-heap" into a "min-heap". You can go in and change the "<"s to ">"s and ">"s to "<"s in a few key places, OR you can multiply the values by -1 before you store them in the heap and after you remove them from the heap.

Choose one of these approaches, and convert your code above into a "min-heap". Test your revised program with N=20 and take a look at the output. Hopefully, you will be removing the data from the heap in increasing value.

Cut and paste the code you modified to make a "min-heap" below:

Cut and paste your final program output below:

This lab assignment will be submitted electronically to the TAs once you fill in the fields below and click on the "submit" button. You do NOT need to print a copy of this document to hand in.

Your full name: | |

Your uaid number: |