How to resolve the algorithm Priority queue step by step in the Logtalk programming language
How to resolve the algorithm Priority queue step by step in the Logtalk programming language
Table of Contents
Problem Statement
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.
Create a priority queue. The queue must support at least two operations:
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:
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.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Priority queue step by step in the Logtalk programming language
Source code in the logtalk programming language
?- logtalk_load(heaps(loader)). % also `{heaps(loader)}.` on most back-ends
% output varies by settings and what's already been loaded
?- heap(<)::new(H0), % H0 contains an empty heap
heap(<)::insert(3, 'Clear drains', H0, H1), % as with Prolog, variables are in the mathematical
% sense: immutable, so we make a new heap from the empty one
heap(<)::insert(4, 'Feed cat',H1, H2), % with each insertion a new heap
heap(<)::top(H2, K2, V2), % K2=3, V2='Clear drains',
% H2=t(2, [], t(3, 'Clear drains', t(4, 'Feed cat', t, t), t))
heap(<)::insert_all(
[
5-'Make tea',
1-'Solve RC tasks',
2-'Tax return'
], H2, H3), % it's easier and more efficient to add items in K-V pairs
heap(<)::top(H3, K3, V3), % K3=1, V3='Solve RC tasks',
% H3=t(5, [], t(1, 'Solve RC tasks', t(3, 'Clear drains',
% t(4, 'Feed cat', t, t), t), t(2, 'Tax return',
% t(5, 'Make tea', t, t), t))),
heap(<)::delete(H3, K3, V3, H4), % K3=1, V3='Solve RC tasks',
% H4=t(4, [5], t(2, 'Tax return', t(3, 'Clear drains',
% t(4, 'Feed cat', t, t), t), t(5, 'Make tea', t, t))),
heap(<)::top(H4, K4, V4). % K4=2, V4='Tax return'
:- object(minheap,
extends(heap(<))).
:- info([
version is 1:0:0,
author is 'Paulo Moura.',
date is 2010-02-19,
comment is 'Min-heap implementation. Uses standard order to compare keys.'
]).
:- end_object.
:- object(maxheap,
extends(heap(>))).
:- info([
version is 1:0:0,
author is 'Paulo Moura.',
date is 2010-02-19,
comment is 'Max-heap implementation. Uses standard order to compare keys.'
]).
:- end_object.
You may also check:How to resolve the algorithm Monte Carlo methods step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Hello world/Standard error step by step in the Déjà Vu programming language
You may also check:How to resolve the algorithm Regular expressions step by step in the REXX programming language
You may also check:How to resolve the algorithm Wordle comparison step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Substring/Top and tail step by step in the F# programming language