CSCE 2014 - Laboratory Assignment 13

    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.

  1. Introduction to Heaps
  2. 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.

  3. The Heap Class
  4. 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];
    };
    

  5. Heap Implementation
  6. 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
    }
    

  7. Testing the Heap Class
  8. 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:

  9. More Testing of Heap
  10. 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:

  11. Extending the Heap Class
  12. 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.

  13. Creating a Min-Heap from a Max-Heap
  14. 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:

  15. Submit Work
  16. 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 UAID number:
    Your website PASSWORD: