Question

In: Computer Science

C++ Implement the array based Binary Heap data structure as discussed in class. This structure should...

C++

Implement the array based Binary Heap data structure as discussed in class. This structure should have a couple of constructures (default constructor, and a constructor that takes an array pointer and a size), a method for inserting items into the heap, a method for removing items from the heap, and a method that returns the number of items currently stored in the heap. This implementation should be templated so that it can store any type of data (you may assume that the <, >, ==, <=, and >= operators are implemented for the type of data being stored). The constructor that takes parameters should set the data structure to use the array passed in as the array for the heap, and then "insert" each item in the array to the heap. You should also throw exceptions where it makes sense to and for the insert method, you should handle the overflow case by increasing the size of the storage.   Remember this should be implemented using Object Oriented Programming principles

Solutions

Expert Solution

#include<iostream>
#include<climits>
using namespace std;

// Prototype of a utility function to swap two integers
void swap(int *x, int *y);

// A class for Min Heap



template <typename T>

class MinHeap
{
        T *harr; // pointer to array of elements in heap
        int capacity; // maximum possible size of min heap
        int heap_size; // Current number of elements in min heap
public:
        // Constructor
        MinHeap(int capacity);

        // to heapify a subtree with the root at given index
        void MinHeapify(int );

        int parent(int i) { return (i - 1) / 2; }

        // to get index of left child of node at index i
        int left(int i) { return (2 * i + 1); }

        // to get index of right child of node at index i
        int right(int i) { return (2 * i + 2); }

        // to extract the root which is the minimum element
        int extractMin();

        // Decreases key value of key at index i to new_val
        void decreaseKey(int i, int new_val);

        // Returns the minimum key (key at root) from min heap
        int getMin() { return harr[0]; }

        // Deletes a key stored at index i
        void deleteKey(int i);

        // Inserts a new key 'k'
        void insertKey(int k);
};

// Constructor: Builds a heap from a given array a[] of given size
template <typename T>

MinHeap<T>::MinHeap(int cap)
{
        heap_size = 0;
        capacity = cap;
        harr = new T[cap];
}

// Inserts a new key 'k'
template <typename T>
void MinHeap<T>::insertKey(int k)
{
        if (heap_size == capacity)
        {
                cout << "\nOverflow: Could not insertKey\n";
                return;
        }

        // First insert the new key at the end
        heap_size++;
        int i = heap_size - 1;
        harr[i] = k;

        // Fix the min heap property if it is violated
        while (i != 0 && harr[parent(i)] > harr[i])
        {
                swap(&harr[i], &harr[parent(i)]);
                i = parent(i);
        }
}

// Decreases value of key at index 'i' to new_val.  It is assumed that
// new_val is smaller than harr[i].
template <typename T>
void MinHeap<T>::decreaseKey(int i, int new_val)
{
        harr[i] = new_val;
        while (i != 0 && harr[parent(i)] > harr[i])
        {
                swap(&harr[i], &harr[parent(i)]);
                i = parent(i);
        }
}

// Method to remove minimum element (or root) from min heap
template <typename T>
int MinHeap<T>::extractMin()
{
        if (heap_size <= 0)
                return INT_MAX;
        if (heap_size == 1)
        {
                heap_size--;
                return harr[0];
        }

        // Store the minimum value, and remove it from heap
        int root = harr[0];
        harr[0] = harr[heap_size - 1];
        heap_size--;
        MinHeapify(0);

        return root;
}


// This function deletes key at index i. It first reduced value to minus
// infinite, then calls extractMin()
template <typename T>
void MinHeap<T>::deleteKey(int i)
{
        decreaseKey(i, INT_MIN);
        extractMin();
}

// A recursive method to heapify a subtree with the root at given index
// This method assumes that the subtrees are already heapified
template <typename T>
void MinHeap<T>::MinHeapify(int i)
{
        int l = left(i);
        int r = right(i);
        int smallest = i;
        if (l < heap_size && harr[l] < harr[i])
                smallest = l;
        if (r < heap_size && harr[r] < harr[smallest])
                smallest = r;
        if (smallest != i)
        {
                swap(&harr[i], &harr[smallest]);
                MinHeapify(smallest);
        }
}

// A utility function to swap two elements
void swap(int *x, int *y)
{
        int temp = *x;
        *x = *y;
        *y = temp;
}

// Driver program to test above functions
int main()
{
        MinHeap<int> h(11);
        h.insertKey(3);
        h.insertKey(2);
        h.deleteKey(1);
        h.insertKey(15);
        h.insertKey(5);
        h.insertKey(4);
        h.insertKey(45);
        cout << h.extractMin() << " ";
        cout << h.getMin() << " ";
        h.decreaseKey(2, 1);
        cout << h.getMin();
        return 0;
}

Related Solutions

C++ Write the code to implement a complete binary heap using an array ( Not a...
C++ Write the code to implement a complete binary heap using an array ( Not a vector ). Code for Max heap. Implement: AddElement, GetMax, HeapSort, ShuffleUp, ShuffleDown, etc Set array size to 31 possible integers. Add 15 elements 1,3,27,22,18,4,11,26,42,19,6,2,15,16,13 Have a default constructor that initializes the array to zeros.. The data in the heap will be double datatype. PART 2 Convert to the program to a template, test with integers, double and char please provide screenshots thank you so...
Language C++ Implement a Priority Queue with a Binary HEAP. Use a Max Heap. Create a...
Language C++ Implement a Priority Queue with a Binary HEAP. Use a Max Heap. Create a class called Node: Have a Name and Priority.Data set - 10 is the highest priority, 1 is lowest priority. Enqueue and dequeue in the following order. Function  Name, Priority Enqueue  Joe, 3 Enqueue  Fred,1 Enqueue Tuyet,9 Enqueue  Jose, 6 Dequeue Enqueue  Jing, 2 Enqueue  Xi, 5 Enqueue  Moe, 3 DequeueEnqueue  Miko, 7 Enqueue Vlady, 8 Enqueue Frank, 9 Enqueue  Anny, 3 DequeueEnqueue  Xi, 2 Enqueue  Wali, 2 Enqueue  xChe, 6 Enqueue  xVerra, 8 Dequeue Dequeue Dequeue Dequeue...
Implement a Binary tree using an array using class.
Implement a Binary tree using an array using class.
Explain this code: The structure used is max heap using array. C++ (i is the index...
Explain this code: The structure used is max heap using array. C++ (i is the index of the element to be deleted) void del(int i) {    int left,right,temp;    arr[i]=arr[n-1];    n=n-1;    left=2*i+1; /*left child of i*/    right=2*i+2; /* right child of i*/    while(right < n)    {        if( arr[i]>=arr[left] && arr[i]>=arr[right] )            return;        if( arr[right]<=arr[left] )        {            temp=arr[i];            arr[i]=arr[left];   ...
Write a C++ class that implement two stacks using a single C++ array. That is, it...
Write a C++ class that implement two stacks using a single C++ array. That is, it should have functions pop_first(), pop_second(), push_first(…), push_second(…), size_first(), size_second(), …. When out of space, double the size of the array (similarly to what vector is doing). Notes: Complete all the functions in exercise_2.cpp, then submit this cpp file. pop_first() and pop_second() should throw std::out_of_range exception when stack is empty. CODE: #include <cstdio> #include <stdexcept> template <class T> class TwoStacks { public:   // Constructor, initialize...
In C++, Implement the heapafication operation. Do not re-implement the binary tree class. Simply create a...
In C++, Implement the heapafication operation. Do not re-implement the binary tree class. Simply create a funcntion that takes in a binary tree and heapafies it. Meaning it takes in a pointer to a binary tree and converts it into a heap. (You may choose max or min heap).
C++ Build a binary tree using a binary tree class member function from the following array...
C++ Build a binary tree using a binary tree class member function from the following array of preorder traversal 3,9,20,15,7 and inorder traversal 9,3,15,20,7. Implement the constructor, destructor and all member functions including print postorder traversal of the binary tree.
Use the Heap class provided to implement a sort routine in a Main class where the...
Use the Heap class provided to implement a sort routine in a Main class where the user enters a series of values, each value is then pushed onto a heap, then the values are printed out in ascending order. public class Heap { public static final int SIZE = 1025; public Heap() { elt = new Element[SIZE]; lastLoc = 0; } public void push(String k, Object o) { if (!fullCheck()) { lastLoc++; elt[lastLoc] = new Element(k,o); int loc = lastLoc;...
you are asked to implement a C++ class to model a sorted array of unsigned integers....
you are asked to implement a C++ class to model a sorted array of unsigned integers. The class is to be used in an embedded application that cannot assume the presence of the STL. The array has to be dynamically allocated in such a way that allows programmers using it to specify the required size. Class will provide (1) provide the appropriate constructors and destructor; (2) provide methods for updating, and showing numbers in/to the array (e.g., to be used...
In this programming project, you will be implementing the data structure min-heap. You should use the...
In this programming project, you will be implementing the data structure min-heap. You should use the C++ programming language, not any other programming language. Also, your program should be based on the g++ compiler on general.asu.edu. All programs will be compiled and graded on general.asu.edu, a Linux based machine. If you program does not work on that machine, you will receive no credit for this assignment. You will need to submit it electronically at the blackboard, in one zip file,...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT