A. Your assignment is to write a heap implementation of integer values, which hi
ID: 3537685 • Letter: A
Question
A. Your assignment is to write a heap implementation of integer values, which highest priority
element is the one with the smallest key value. The implementation uses a minimum heap. You
need to modify the heap operations to keep the minimum, rather than maximum, element in the
root.
Sample input/output:
How many elements you have initially: 6
Enter the elements: 23 6 87 9 29 12
The heap is: 6 9 12 23 29 87
Press 1 for insert, press 2 for delete, or press 3 to exit program: 1
Enter the element: 29
The new heap is: 6 9 12 23 29 87 29
Press 1 for insert, press 2 for delete, or press 3 to exit program: 1
Enter the element: 7
The new heap is: 6 7 12 9 29 87 29 23
Press 1 for insert, press 2 for delete, or press 3 to exit program: 2
The deleted element is: 6
The new heap is: 7 9 12 23 29 87 29
Press 1 for insert, press 2 for delete, or press 3 to exit program: 2
The deleted element is: 7
The new heap is: 9 23 12 29 29 87
Press 1 for insert, press 2 for delete, or press 3 to exit program: 3
exit
B. Implement the following sorting algorithms for integer values and determine required time
for each algorithm:
(i) SelectionSort
(ii) BubbleSort
(iii) ShortBubbleSort
(iv) InsertionSort
(v) MergeSort
(vi) QuickSort
(vii) HeapSort
Sample input/output:
Enter the number of integer elements: 100
Enter the elements: %u2026
SelectionSort results: (elements in order)
Required time: %u2026 microseconds
BubbleSort results: (elements in order)
Required time: %u2026 microseconds
ShortBubbleSort results: (elements in order)
Required time: %u2026 microseconds
InsertionSort results: (elements in order)
Required time: %u2026 microseconds
MergeSort results: (elements in order)
Required time: %u2026 microseconds
QuickSort results: (elements in order)
Required time: %u2026 microseconds
HeapSort results: (elements in order)
Required time: %u2026 microseconds
Explanation / Answer
//POSTING FIRST PART WILL POST SECOND PART SHORTLY
#include <iostream>
#include <vector>
#include <iterator>
#include <string>
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);
void heapifyup(int index);
void heapifydown(int index);
private:
vector<int> heap;
};
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();
while ( pos != heap.end() ) {
cout << *pos << " ";
++pos;
}
cout << endl;
}
void Heap::heapifyup(int index)
{
//cout << "index=" << index << endl;
//cout << "parent(index)=" << parent(index) << endl;
//cout << "heap[parent(index)]=" << heap[parent(index)] << endl;
//cout << "heap[index]=" << heap[index] << endl;
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)
{
//cout << "index=" << index << endl;
//cout << "left(index)=" << left(index) << endl;
//cout << "right(index)=" << right(index) << endl;
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 h;
int num,ch,tmp;
cout<<"How many elements you have initially:" ;
cin>>num;
cout<<"Enter the elements:";
for(int i=0;i<num;i++)
{
cin>>tmp;
h.insert(tmp);
}
cout<<"The heap is:";
h.print();
while(1)
{
cout<< "Press 1 for insert, press 2 for delete, or press 3 to exit program: ";
cin>>ch;
switch(ch)
{
case 1 : cout<<" Enter the element: ";
cin>>tmp;
h.insert(tmp);
cout<<"The new heap is:";
h.print();
break;
case 2 :
cout<<"The deleted element is:";
cout<<h.deletemin()<<endl;
cout<<"The new heap is:";
h.print();
break;
case 3 :
cout<<"Exit"<<endl;
//system("pause");
return 0;
break;
default:
cout<<"Please enter valid choice"<<endl;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.