**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Priority queue

Summary

In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure. Each element in a priority queue has an associated priority. In a priority queue, elements with high priority are served before elements with low priority. In some implementations, if two elements have the same priority, they are served in the same order in which they were enqueued. In other implementations, the order of elements with the same priority is undefined.
While priority queues are often implemented using heaps, they are conceptually distinct from heaps. A priority queue is an abstract data structure like a list or a map; just as a list can be implemented with a linked list or with an array, a priority queue can be implemented with a heap or another method such as an unordered array.
Operations
A priority queue must at least support the following operations:

- is_empty: check whether the queue has no elements.
- insert_with_priority: add an e

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people

No results

Related units

No results

Related publications (19)

Loading

Loading

Loading

Related concepts (25)

Heap (data structure)

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P

Collection (abstract data type)

In computer programming, a collection is a grouping of some variable number of data items (possibly zero) that have some shared significance to the problem being solved and need to be operated upon

Stack (abstract data type)

In computer science, a stack is an abstract data type that serves as a collection of elements, with two main operations:

- Push, which adds an element to the collection, and
- Pop, which removes th

Related courses (9)

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

CS-305: Software engineering

This course teaches the basics of modern software development: designing software, working in a team, writing good code, shipping software, and evolving software. It emphasizes building software that meets high standards of quality, reliability, security, and manageability.

CS-430: Intelligent agents

Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by programming exercises, and the theoretical underpinnings including computational game theory.

Related lectures (24)

The context of this thesis is the interactive manipulation of complex articulated figures by means of geometric constraints (here called tasks), for the purpose of posture control and design. The goal is to determine a posture satisfying a set of prescribed tasks, usually expressed in the Cartesian space. This approach is known as Inverse Kinematics, and a number of analytic and numerical resolution methods have been developed for the control of robot manipulators. These methods have been applied to the computer animation of articulated figures, and to the control of human models for computer-aided ergonomic evaluations of products or workplaces. When dealing with figures that possess a large number of degrees of freedom, such as animal or human figures, their posture is usually controlled by several simultaneous tasks. There are tasks of different nature and function: they can control extremities such as the hands and the feet (for reaching or supporting purposes), as well as the center of mass, for balance control. They can also be used to avoid collisions with surrounding obstacles. The concurrent resolution of multiple tasks inevitably leads to conflicts that must be resolved with an appropriate strategy. A typical policy is to find a compromise solution that considers weights assigned to each task to indicate their relative importance. However, no task is precisely satisfied with this approach, and selecting appropriate weights is not always straightforward. In this thesis, we introduce a priority strategy for conflict resolution. With this policy, a task is not affected by other tasks of lower priority, and is satisfied as much as possible without affecting tasks of higher priority. The relative priority between two tasks is thus strictly enforced, which is appropriate for situations that cannot tolerate compromises. For example, keeping balance is more important than reaching an object with a hand, and avoiding inter-penetration of bodies is more important than any other task. Priorities are well-suited to express such hierarchical relationships. Based on a task-priority algorithm developed in robotics for simple manipulators, we introduce a framework that integrates the two conflict resolution strategies: first, the priorities assigned to the tasks are considered and, second, a weighting strategy solves the conflicts between tasks having same priority. We have improved the efficiency of the original algorithm by means of recursive relations, which is beneficial for interactive applications. Joint limits and joint couplings are also integrated in the framework to avoid unfeasible body postures. An interactive application, called BALANCE, has been developed to test the algorithm with a palette of task types: it allows us to illustrate the utility of task priorities for the manipulation of generic articulated figures, and of human models in particular. Besides simple geometric tasks, the application also proposes a task to keep the figure balanced under a set of static forces due to the interaction with its environment. It is shown that this task is easily integrated in the inverse kinematics framework, and that it is useful to generate postures in multiple supports with force exertions such as push and pull activities.

,

Probability distributions are key components of many learning from demonstration (LfD) approaches, with the spaces chosen to represent tasks playing a central role. Although the robot configuration is defined by its joint angles, end-effector poses are often best explained within several task spaces. In many approaches, distributions within relevant task spaces are learned independently and only combined at the control level. This simplification implies several problems that are addressed in this work. We show that the fusion of models in different task spaces can be expressed as products of experts (PoE), where the probabilities of the models are multiplied and renormalized so that it becomes a proper distribution of joint angles. Multiple experiments are presented to show that learning the different models jointly in the PoE framework significantly improves the quality of the final model. The proposed approach particularly stands out when the robot has to learn hierarchical objectives that arise when a task requires the prioritization of several sub-tasks (e.g. in a humanoid robot, keeping balance has a higher priority than reaching for an object). Since training the model jointly usually relies on contrastive divergence, which requires costly approximations that can affect performance, we propose an alternative strategy using variational inference and mixture model approximations. In particular, we show that the proposed approach can be extended to PoE with a nullspace structure (PoENS), where the model is able to recover secondary tasks that are masked by the resolution of tasks of higher-importance.

Ricardo Bianchini, Maria Fernanda Borge Chavez, Willy Zwaenepoel

Distributed file systems often exhibit high tail latencies, especially in large-scale datacenters and in the presence of competing (and possibly higher priority) workloads. This paper introduces techniques for managing tail latencies in these systems, while addressing the practical challenges inherent in production datacenters (e.g., hardware heterogeneity, interference from other workloads, the need to maximize simplicity and maintainability). We implement our techniques in a scalable distributed file system (an extension of HDFS) used in production at Microsoft. Our evaluation uses 70k servers in 3 datacenters, and shows that our techniques reduce tail latency significantly for production workloads.