Build the following program so that it creates a heap data structure and impleme

Question

Build the following program so that it creates a heap data structure and implements it to add items to the heap,displays the heap as a vector and lists the minimum values. Carefully examine the methods and functions. Make changes to it to explore how the program functions. Think about ways you could use this data structure to solve a real world problem.

#include <iostream>

#include <vector>

#include <iterator>

using namespace std;

class Heap {

public:

Heap();

~Heap();

void insert(int element);

int deletemin();

void print();

int size() { return heap.size(); }

private:

int left (int parent);

int right (int parent);

int parent (int child);

viod heapifyup(int index);

void heapifydown(int index);

};

Heap::Heap(){ }

Heap::~Heap(){ }

void Heap::insert(int element){

heap.push_back(element);

heapifyup(heap.size() - 1);

}

int Heap::deletemin(){

int min = heap.front();

heap[0] = heap.at(heap.size() -1);

heap.pop_back();

heapifydown(0);

return min;

}

void Heap::print(){

vector<int>::iterator pos = heap.begin();

cout << "Heap = ";

while ( pos != heap.end() ) {

cout << *pos << " ";

++pos;

}

cout << endl;

}

void Heap::heapifyup(int index){

while ( ( index > 0 ) && ( parent(index) >= 0 ) && ( heap[parent(index)] > heap[index] ) ) {

int tmp = heap[parent(index)];

heap[parent(index)] = heap[index];

heap[index] = tmp;

index = parent(index);

}

}

void Heap::heapifdown(int index){

int child = left(index);

if ( ( child > 0 ) && ( right(index) > 0 ) && ( heap[child] > heap[right(index)] ) ) {

child = right(index);

}

if ( child > 0) {

int tmp = heap[index];

heap[index] = heap[child];

heap[child] = tmp;

heapifydown(child);

}

}

int Heap::left(int parent) {

int i = ( parent << 1 ) + 1; // 2*parent +1

return ( i < heap.size() ) ? i : -1;

}

int Heap::right(int parent) {

int i = ( parent << 1 ) + 2; // 2*parent +2

return ( i < heap.size() ) ? i : -1;

}

int Heap::parent(int child) {

if(child != 0) {

int i = (child - 1) >> 1;

return i;

}

return -1;

}

int main(){

// Create the heap

Heap* myheap = new Heap();

myheap->insert(700);

myheap->print();

myheap->insert(500);

myheap->print();

myheap->insert(100);

myheap->print();

myheap->insert(800);

myheap->print();

myheap->insert(200);

myheap->print();

myheap->insert(400);

myheap->print();

myheap->insert(900);

myheap->print();

myheap->insert(1000);

myheap->print();

myheap->insert(300);

myheap->print();

myheap->insert(600);

myheap->print();

// Get priority element from the heap

int heapSize = myheap->size();

for ( int i = 0; i < heapSize; i++ )

cout << "Get min element = " << myheap->deletemin() << endl;

// Cleanup

delete my heap;

}

Explanation / Answer

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
class Heap {
   private:
       vector<int> heap;
   public:
       Heap();
       ~Heap();
       void insert(int element);
       int deletemin();
       void print();
       int size() { return heap.size(); }
       private:
       int left (int parent);
       int right (int parent);
       int parent (int child);
       void heapifyup(int index);
       void heapifydown(int index);
};

Heap::Heap(){ }
Heap::~Heap(){ }
void Heap::insert(int element){
   heap.push_back(element);
   heapifyup(heap.size() - 1);
}
int Heap::deletemin(){
   int min = heap.front();
   heap[0] = heap.at(heap.size() -1);
   heap.pop_back();
   heapifydown(0);
   return min;
}
void Heap::print(){
   vector<int>::iterator pos = heap.begin();
   cout << "Heap = ";
   while ( pos != heap.end() ) {
       cout << *pos << " ";
       ++pos;
   }
   cout << endl;
}
void Heap::heapifyup(int index){
   while ( ( index > 0 ) && ( parent(index) >= 0 ) && ( heap[parent(index)] > heap[index] ) ) {
       int tmp = heap[parent(index)];
       heap[parent(index)] = heap[index];
       heap[index] = tmp;
       index = parent(index);
   }
}
void Heap::heapifydown(int index){
   int child = left(index);
   if ( ( child > 0 ) && ( right(index) > 0 ) && ( heap[child] > heap[right(index)] ) ) {
       child = right(index);
   }
   if ( child > 0) {
       int tmp = heap[index];
       heap[index] = heap[child];
       heap[child] = tmp;
       heapifydown(child);
   }
}
int Heap::left(int parent) {
   unsigned int i = ( parent << 1 ) + 1; // 2*parent +1
   return ( i < heap.size() ) ? i : -1;
}
int Heap::right(int parent) {
   unsigned int i = ( parent << 1 ) + 2; // 2*parent +2
   return ( i < heap.size() ) ? i : -1;
}
int Heap::parent(int child) {
   if(child != 0) {
       int i = (child - 1) >> 1;
       return i;
   }
   return -1;
}
int main(){
   // Create the heap
   Heap* myheap = new Heap();
   myheap->insert(700);
   myheap->print();
   myheap->insert(500);
   myheap->print();
   myheap->insert(100);
   myheap->print();
   myheap->insert(800);
   myheap->print();
   myheap->insert(200);
   myheap->print();
   myheap->insert(400);
   myheap->print();
   myheap->insert(900);
   myheap->print();
   myheap->insert(1000);
   myheap->print();
   myheap->insert(300);
   myheap->print();
   myheap->insert(600);
   myheap->print();
   // Get priority element from the heap
   int heapSize = myheap->size();
   for ( int i = 0; i < heapSize; i++ )
       cout << "Get min element = " << myheap->deletemin() << endl;
   // Cleanup
   delete myheap;
}

/*

Output:

Heap = 700
Heap = 500 700
Heap = 100 700 500
Heap = 100 700 500 800
Heap = 100 200 500 800 700
Heap = 100 200 400 800 700 500
Heap = 100 200 400 800 700 500 900
Heap = 100 200 400 800 700 500 900 1000
Heap = 100 200 400 300 700 500 900 1000 800
Heap = 100 200 400 300 600 500 900 1000 800 700
Get min element = 100
Get min element = 200
Get min element = 300
Get min element = 400
Get min element = 500
Get min element = 600
Get min element = 700
Get min element = 800
Get min element = 900
Get min element = 1000

*/

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.