Create a priority queue of characters by implementing min-heap data structure. P
ID: 3548573 • Letter: C
Question
Create a priority queue of characters by implementing min-heap data structure. Provide a menu then test insert, findmin, removeMin, and display function. Sample output is as follows.<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
Algorithm: InsertItem(v)
add v as next leaf
while v<parent(v) {
swapElements(v,parent(v))
v=parent(v)
}
Algorithm: RemoveMin()
temp = value of root
swap root value with last leaf
delete last leaf
v = root
while v > any child(v) {
swapElements(v, smaller child(v))
v= smaller child(v)
}
return temp
Sample output:
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
1
Enter data: d
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
1
Enter data: e
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
1
Enter data: a
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
1
Enter data: c
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
1
Enter data: b
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
4
the elements in the priority queue are:
a b d e c
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
3
Minimum char is: a
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
2
a is deleted
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
4
the elements in the priority queue are:
b c d e
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
3
Minimum char is: b
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
2
b is deleted
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
4
the elements in the priority queue are:
c e d
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
5
Press any key to continue . . .
Explanation / Answer
#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);
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();
cout << "Heap = ";
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* 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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.