Assume we use a heap to implement a priority queue: we insert elements into the
ID: 3682240 • Letter: A
Question
Assume we use a heap to implement a priority queue: we insert elements into the queue and remove elements in the order of their priority (max priority first). Assume we want to ensure that we remove elements in the FIFO order within a given priority. In other words, for any two elements with the same priority, the element that was inserted first will be removed first. The methods involved in the heap insertion and removal are “void insert(T item)”, “T removeMax()”, “void siftUp(int i)”, and “void siftDown(int i)”. Write these methods to support the above functionality.
Explanation / Answer
void BinaryHeap::Insert(int element)
{
heap.push_back(element);
heapifyup(heap.size() -1);
}
void BinaryHeap::DeleteMax()
{
if (heap.size() == 0)
{
cout<<"Heap is Empty"<<endl;
return;
}
heap[0] = heap.at(heap.size() - 1);
heap.pop_back();
heapifydown(0);
cout<<"Element Deleted"<<endl;
}
void BinaryHeap::siftUp(int in)
{
if (in >= 0 && parent(in) >= 0 && heap[parent(in)] > heap[in])
{
int temp = heap[in];
heap[in] = heap[parent(in)];
heap[parent(in)] = temp;
heapifyup(parent(in));
}
}
void BinaryHeap::siftDown(int in)
{
int child = left(in);
int child1 = right(in);
if (child >= 0 && child1 >= 0 && heap[child] > heap[child1])
{
child = child1;
}
if (child > 0)
{
int temp = heap[in];
heap[in] = heap[child];
heap[child] = temp;
heapifydown(child);
}
}
int BinaryHeap::left(int parent)
{
int l = 2 * parent + 1;
if (l < heap.size())
return l;
else
return -1;
}
int BinaryHeap::right(int parent)
{
int r = 2 * parent + 2;
if (r < heap.size())
return r;
else
return -1;
}