A priority queue is somewhat similar to a queue, with an important distinction: each item is added to a priority queue with a priority level, and will be later removed from the queue with the highest priority element first. That is, the items are (conceptually) stored in the queue in priority order instead of in insertion order.



Task

Create a priority queue.   The queue must support at least two operations:

   Insertion.   An element is added to the queue with a priority (a numeric value).
   Top item removal.   Deletes the element or one of the elements with the current top priority and return it.


Optionally, other operations may be defined, such as peeking (find what current top priority/top element is), merging (combining two priority queues into one), etc.



To test your implementation, insert a number of elements into the queue, each with some random priority.

Then dequeue them sequentially; now the elements should be sorted by priority.

You can use the following task/priority items as input data:

        Priority         Task
       ══════════   ════════════════
           3         Clear drains
           4         Feed cat
           5         Make tea
           1         Solve RC tasks
           2         Tax return



The implementation should try to be efficient.   A typical implementation has   O(log n)   insertion and extraction time,   where   n   is the number of items in the queue.

You may choose to impose certain limits such as small range of allowed priority levels, limited capacity, etc.   If so, discuss the reasons behind it.




mata
	struct Node {
		real scalar time
		transmorphic data
		}
	class Heap {
		public:
		struct Node rowvector nodes
		real scalar len
		real scalar size
		real scalar minHeap
		void new()
		void push()
		void siftup()
		void siftdown()
		struct Node scalar pop()
		real scalar empty()
		real scalar compare()
		}
	real scalar Heap::compare(a,b) {
		struct Node scalar left, right
		left = nodes[a]
		right = nodes[b]
		return(minHeap ? left.time<right.time : left.time>right.time)
		}
	void Heap::new()  {
		len = 0
		size = 4
		nodes = Node(1,size)
		minHeap = 1 // defaults to min heap
		}
	real scalar Heap::empty() {
		return(len==0)
		}
	void Heap::siftdown(real scalar index) {
		parent = index
		while (parent*2 <= len) {
			child = parent*2
			if (child+1 <= len ? compare(child+1,child) : 0) {
				child++
				}
			if (compare(child,parent)) {
				nodes[(child,parent)] = nodes[(parent,child)]
				parent = child
				} else break
			}
		}
	void Heap::siftup(real scalar index) {
		child = index
		while(child>1) {
			parent = floor(child/2)
			if (compare(parent,child)) {
				break
				}
			nodes[(child,parent)] = nodes[(parent,child)]
			temp = child
			child = parent
			parent = temp
			}
		}
	void Heap::push (real scalar time, transmorphic data) {
		if (len + 1 >= size) {
			nodes = (nodes, nodes)
			size = size*2
			}
		len++
		nodes[len].time = time
		nodes[len].data = data
		siftup(len)
		}
	struct Node scalar Heap::pop () {
		if (len==0) {
			_error(3000,"empty heap")
			}
		len--
		struct Node scalar newnode
		newnode.time = nodes[1].time
		newnode.data = nodes[1].data
		if (len>0) {
			nodes[1] = nodes[len+1]
			siftdown(1)
			}
		return(newnode)
		}
	void testHeap(real scalar minHeap) {
		class Heap scalar h
		struct Node scalar node 
		h = Heap()
		h.minHeap = minHeap
		h.push(3, "Clear drains")
		h.push(4, "Feed cat")
		h.push(5, "Make tea")
		h.push(1, "Solve RC tasks")
		h.push(2, "Tax return")
		while (!h.empty()) {
			node = h.pop()
			printf("%f -> %s\n", node.time, node.data)
			}
		}
	testHeap(1)
	testHeap(0)
end
 