Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Purely Functional Priority Queue

Description

This lecture covers the optimal purely functional priority queues, starting with an overview of imperative and purely functional implementations, followed by Scala implementation and testing, Stainless integration, operations properties, and binomial queues. The presentation also includes results, future works, and explicit requirements for binomial queues.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Related concepts (22)

Binomial heap

In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged. It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which is a priority queue supporting merge operation. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.

Fibonacci heap

In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap. Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis.

Priority queue

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.

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 is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node. The heap is one maximally efficient implementation of an abstract data type called a priority queue, and in fact, priority queues are often referred to as "heaps", regardless of how they may be implemented.

Associative property

In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement for expressions in logical proofs. Within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not changed.

Related lectures (37)

Matrix Multiplication and Heaps: Efficient Algorithms

Discusses Strassen's algorithm for matrix multiplication and heaps, covering efficient algorithms and their applications in computer science.

Conc-Trees: Parallel Programming in Scala

Covers the implementation of Conc-Trees in Scala for parallel programming.

A Closer Look at Lists

Covers list construction, methods, and implementations, including exercises and complexity analysis.

Matrix Multiplication and Divide-and-Conquer Techniques

Discusses matrix multiplication using divide-and-conquer techniques and introduces Strassen's algorithm for improved efficiency.

Stainless Verification System Tutorial