Question

PROGRAM DESCRIPTION

Using the given class definitions for either C++, create a minimum heap that stores integers and and implements a minimum priority queue. (Your program can be "hard coded" for integers - it does not need to use templates, generics, or polymorphism.)

Your data structure must always store its internal data as a heap.

Your toString function should return a string with the heap values as a comma separated list, also including the size of the heap as well. toString must show the values in the same ordering as they are in the array/heap.

Your heapsort function should create a new array with the sorted values and not modify the heap. That resulting array must be sized to exactly hold the number of elements in the result. Since this is a minimum heap, the heap sort should generate data in descending order.

Your heapinsert function should return false if you try to insert values into a full heap (and return true on a sucessful insert.) minimum and extractMinimum should return 0 on an empty heap.

You are required to implement and use parent(i), left(i), and right(i) helper functions. I also recommend use of a "minimum of three" helper function as dscribed in class.

Don't forget a bounds checks as needed. (In general, make sure that all of your public functions are robust!)

For this assingment, please create a zero-based heap (where A[0] is the root) as described in class, and not a one-based heap (where A[1] is the root) as described in the textbook.

You may make minor adjustments to the class definitions (for example, adding extra helper functions or overloading the constructor to accept initial values,) but any major changes must have prior approval in writing (do this via email.)

// integer minimum heap with PQ 
class intMinHeap{
public:
  intMinHeap(int);  // empty heap wth this capacity
  ~intMinHeap();  // clean up allocated memory  
  int *heapsort();  // return sorted array from heap
  string toString();  
  bool heapinsert(int); // add element to heap; return success
  // min functions should return 0 in empty heaps 
  int minimum();  // return value of A[root]
  int extractmin(); // return and remove A[root]
  void decreasekey(int i, int k);  // A[i] decreased to k
  bool isEmpty(){return size==0;}
  bool isFull();  
private:
  int minOf3(int, int, int); // with bounds check!
  int left(int);
  int right(int);
  int parent(int);      
  void buildheap();  // convert array to a heap
  void heapify(int i);  // heapify at position i  
  int *A;  // array of integers - data
  int capacity; // size of array A
  int size; // data size in array
 };

class intMinHeap implements Serializable{
  public intMinHeap(int cap){ ... }
  public int [] heapsort(){ ... }
  public String toString(){ ... }
  public bool heapinsert(int n){ ... }  
  public int minimum(){ ... } // A[root] or 0 if empty
  public int extractMin(){ ... } // A[root] or 0
  public void decreaseKey(int i, int k){ ... }           
  public boolean isEmpty(){ ... }
  public boolean isFull(){ ... }
  private void buildheap(){ ... }
  private int minOf3(int, int, int){ ... }
  private int left(int i){ ... }
  private int right(int i){ ... }
  private int parent(int i){ ... }
  private void heapify(int i){ ... } // at position i    
  private int [] A;
  private int capacity; // size of array A
  private int size; // size of data in array A
}

MAIN PROGRAM TESTING

Create a "main" to test your data structure. Create a heap/pq with capacity of 2,400,000. Your main function will have some strange i/o as described below.

Your main function should read all input from STDIN (until EOF.) Each line will consist of a single integers.

Perform the following operations, depending on the value input.

if the input value is a positive integer (greater than zero,) insert it into your object. This operation prints "insert" and the value that was added.

if the input value is a zero, print the heap and the size of the heap on a single line of text (as a comma seperated list.) see the provided example for the exact syntax to follow.

If the input value is a -1, extract the minimum value from your object, and print that value on a single line.

If the input value is a -2, call heapsort, and then print, on a single line, as a comma-sperated list the sorted array returned from heapsort.

Your output formatting must be identical to the provided sample.

INPUT EXAMPLE

2
9
4
7
5
8
6
10
3
1
0
-1
-1
0
1
0
-2
0

OUTPUT EXAMPLE

insert: 2
insert: 9
insert: 4
insert: 7
insert: 5
insert: 8
insert: 6
insert: 10
insert: 3
insert: 1
heap size 10: 1, 2, 4, 5, 3, 8, 6, 10, 9, 7
extract min: 1
extract min: 2
heap size 8: 3, 5, 4, 9, 7, 8, 6, 10
insert: 1
heap size 9: 1, 3, 4, 5, 7, 8, 6, 10, 9
sorted array: [10, 9, 8, 7, 6, 5, 4, 3, 1]
heap size 9: 1, 3, 4, 5, 7, 8, 6, 10, 9

Answer 1

intMinHeap.cpp

#include <iostream>
#include "intMinHeap.h"

using std::to_string;
using std::cout;
using std::cerr;
using std::endl;

intMinHeap::intMinHeap(int c) {
size = 0;
capacity = c;
A = new int[capacity];
}

intMinHeap::~intMinHeap() {
delete [] A;
}

int* intMinHeap::heapsort() {
buildheap();
int* sortCopy = new int[size];
int heapSize = size; //maintain original heap size
for (int i = 0; i < size; i++)   //hard copy
    sortCopy[i] = A[i];
int* temp = A;
A = sortCopy;
for (int i = size - 1; i > 0; i--) {
    swap(0, i);
    size--;
    heapify(0);
}
A = temp;
size = heapSize;
return sortCopy;
}

string intMinHeap::toString() {
string str = "heap size " + to_string(size) + ": ";
for (int i = 0; i < size - 1; i++)
    str += (to_string(A[i]) + ", ");
str += to_string(A[size - 1]);
return str;
}

bool intMinHeap::heapinsert(int key) {
if (isFull()) return false;
A[size] = key + 1;
size++;
decreasekey(size-1, key);
return true;
}

int intMinHeap::minimum() {
if (isEmpty()) return 0;
return A[0];
}

int intMinHeap::extractmin() {
if (isEmpty()) {
    cerr << "Warning: extractmin() called on empty heap; 0 returned" << endl;
    return 0;
}
int min = A[0];
A[0] = A[size - 1];
size--;
heapify(0);
return min;
}

void intMinHeap::decreasekey(int index, int key) {
if (index >= size) {
    cerr << "Warning: index out of range—No element exists "
    "at specified index." << endl;
    return;
}
if (A[index] <= key) return;
A[index] = key;
while (index > 0 && A[parent(index)] > A[index]) {
    swap(index, parent(index));
    index = parent(index);
}
}

int intMinHeap::minOf3(int index, int left, int right) {
int minIndex = index;
if (left <= (size - 1) && A[left] < A[minIndex])
    minIndex = left;
if (right <= (size - 1) && A[right] < A[minIndex])
    minIndex = right;
return minIndex;
}

void intMinHeap::swap(int i, int n) {
int temp = A[i];
A[i] = A[n];
A[n] = temp;
}

int intMinHeap::left(int index) {
return 2*index + 1;
}

int intMinHeap::right(int index) {
return 2*index + 2;
}

int intMinHeap::parent(int index) {
return (index - 1)/2;
}

void intMinHeap::buildheap() {
for (int i = size/2 - 1; i >= 0; i--)
    heapify(i);
}

void intMinHeap::heapify(int index) {
int minIndex = minOf3(index, left(index), right(index));
if (index != minIndex) {
    swap(index, minIndex);
    heapify(minIndex);
}
}

intMinHeap.h

#ifndef INTMINHEAP_H
#define INTMINHEAP_H

#include <string>

using std::string;

// This class implements a minimum heap priority queue.
// Objects of this class store integers in a ZERO-BASED
// (root at A[0]) heap—-the minimum heap property is
// always maintained.
class intMinHeap {

public:
// create an empty heap wth capacity c, size 0
intMinHeap(int c);

// clean up allocated memory
~intMinHeap();

// Returns sorted array from heap. Maintains original heap and returns
// pointer to newly allocated sorted array. NOTE: this function
// allocates an array using the "new" keyword; user is responsible for
// deallocating the array using the "delete []" keyword. Returns empty
// array when called on empty heap.
int *heapsort();

// returns string containing heap values in order in a comma separated
// list, as well as heap size. returns "heap size 0: " if called on empty
// heap.
string toString();

// add element to heap; return success
bool heapinsert(int);

// return value of A[root]
int minimum();

// return and remove A[root]
int extractmin();

// A[i] decreased to k
void decreasekey(int i, int k);

// check for empty heap
bool isEmpty(){return size==0;}

// check if array is full/heap is at capacity
bool isFull(){return size==capacity;}

// return size of heap
int getSize() const {return size;}

private:
int minOf3(int i, int l, int r); // index of lowest value of A[i], A[l], and A[r]
void swap(int i, int n); //swap array elements with indices i and n
int left(int); // index of left
int right(int); // index of right
int parent(int); // index of parent
void buildheap(); // convert array to a heap
void heapify(int i); // heapify at position i
int *A; // array of integers - data
int capacity; // size of array A
int size; // data size in array

};

#endif

main.cpp

#include <iostream>
#include "intMinHeap.h"

using std::cin;
using std::cout;
using std::endl;

int main() {
intMinHeap testHeap(2400000);
int* testSort;
int size;
int input;
while (cin >> input) {
    if (input > 0) {
      testHeap.heapinsert(input);
      cout << "insert: " << input << endl;
    }
    if (input==0)
      cout << testHeap.toString() << endl;
    if (input == -1)
      cout << "extract min: " << testHeap.extractmin() << endl;
    if (input == -2) {
      testSort = testHeap.heapsort();
      size = testHeap.getSize();
      cout << "sorted array: [";
      for (int i = 0; i < size-1; i++)
   cout << testSort[i] << ", ";
      cout << testSort[size-1] << "]" << endl;
      delete [] testSort;
    }
}
}