C++ assignment help. Please post output as well Your assignment is to write and
ID: 3849786 • Letter: C
Question
C++ assignment help. Please post output as well
Your assignment is to write and compare two implementations of a priority queue whose highest priority element is the one with the smallest key value. The elements have the following declarations:
The first implementation uses a minimum heap. You need to modify the heap operations to keep the minimum, rather than maximum, element in the root. The comparison function should compare key fields.
The second implementation uses a linear linked list, whose elements are ordered by key value.
Test Data
Create a data set that contains 50 items with priorities generated by a random-number generator.
Comparing the Implementations
To compare the operations, you must modify the Enqueue and Dequeue operations to count how many elements are accessed (compared or swapped, in the case of reheaping) during its execution.
Write a driver to Enqueue and Dequeue the 50 test items and print out the number of elements accessed for the Enqueue and Dequeue operations. Run your driver once with each implementation.
Explanation / Answer
There are a variety of ways priority queue can be implemented. A very simple and naive implementation is to use sorted or unsorted list, but this is not efficient. More efficient implementations are based on heap data structure. Heap is a tree-based data structure with the min-heap or max-heap property. Min-heap property means that key of every child node should be greater or equal to the key of parent node. Max-heap property means that the key of every child node should be less or equal to the key of parent node.
In my implementation, I used min-binary heap. Binary heap can be efficiently stored in the array, despite the fact that heap is a tree-based structure. If we use zero-based array arr to store binary heap data, then node at arr[i] will have children nodes arr[2*i + 1] and arr[2*i + 2], and parent node arr[(i-1)/2].
public class PriorityQueue<TPriority, TValue>
{
private List<KeyValuePair<TPriority, TValue>> _baseHeap;
private IComparer<TPriority> _comparer;
public PriorityQueue()
: this(Comparer<TPriority>.Default)
{
}
public PriorityQueue(IComparer<TPriority> comparer)
{
if (comparer == null)
throw new ArgumentNullException();
_baseHeap = new List<KeyValuePair<TPriority, TValue>>();
_comparer = comparer;
}
// ... other code
}
Enqueue and Dequeue Operations:
public void Enqueue(TPriority priority, TValue value)
{
Insert(priority, value);
}
private void Insert(TPriority priority, TValue value)
{
KeyValuePair<TPriority, TValue> val =
new KeyValuePair<TPriority, TValue>(priority, value);
_baseHeap.Add(val);
// heapify after insert, from end to beginning
HeapifyFromEndToBeginning(_baseHeap.Count - 1);
}
private int HeapifyFromEndToBeginning(int pos)
{
if (pos >= _baseHeap.Count) return -1;
// heap[i] have children heap[2*i + 1] and heap[2*i + 2] and parent heap[(i-1)/ 2];
while (pos > 0)
{
int parentPos = (pos - 1) / 2;
if (_comparer.Compare(_baseHeap[parentPos].Key, _baseHeap[pos].Key) > 0)
{
ExchangeElements(parentPos, pos);
pos = parentPos;
}
else break;
}
return pos;
}
private void ExchangeElements(int pos1, int pos2)
{
KeyValuePair<TPriority, TValue> val = _baseHeap[pos1];
_baseHeap[pos1] = _baseHeap[pos2];
_baseHeap[pos2] = val;
}
public TValue DequeueValue()
{
return Dequeue().Value;
}
public KeyValuePair<TPriority, TValue> Dequeue()
{
if (!IsEmpty)
{
KeyValuePair<TPriority, TValue> result = _baseHeap[0];
DeleteRoot();
return result;
}
else
throw new InvalidOperationException("Priority queue is empty");
}
private void DeleteRoot()
{
if (_baseHeap.Count <= 1)
{
_baseHeap.Clear();
return;
}
_baseHeap[0] = _baseHeap[_baseHeap.Count - 1];
_baseHeap.RemoveAt(_baseHeap.Count - 1);
// heapify
HeapifyFromBeginningToEnd(0);
}
private void HeapifyFromBeginningToEnd(int pos)
{
if (pos >= _baseHeap.Count) return;
// heap[i] have children heap[2*i + 1] and heap[2*i + 2] and parent heap[(i-1)/ 2];
while (true)
{
// on each iteration exchange element with its smallest child
int smallest = pos;
int left = 2 * pos + 1;
int right = 2 * pos + 2;
if (left < _baseHeap.Count &&
_comparer.Compare(_baseHeap[smallest].Key, _baseHeap[left].Key) > 0)
smallest = left;
if (right < _baseHeap.Count &&
_comparer.Compare(_baseHeap[smallest].Key, _baseHeap[right].Key) > 0)
smallest = right;
if (smallest != pos)
{
ExchangeElements(smallest, pos);
pos = smallest;
}
else break;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.