Priority Queues and Binomial Heaps (Algorithms)

Опубликовано: 26 Январь 2021
на канале: Frank Stajano Explains

1,878

I am a Professor in the Computer Science department at the University of Cambridge. Through this channel I welcome anyone in the world to attend my lectures. This video is part of my first-year Algorithms course.

The Priority Queue is a data structure that allows efficient retrieval of the item with the highest priority (say, the item with the numerically smallest key). We have already studied and used a good implementation of the priority queue, in the form of the binary heap, which has logarithmic cost for most of its operations.

One operation that has greater than logarithmic cost with a binary heap is merging two such heaps. This will have linear cost. In today's video we introduce a variant on the binary heap, called the binomial heap, which preserves the logarithmic cost for the usual binary heap operations but also offers logarithmic cost for merging. It will also be a building block for an even more elaborate priority queue, the amazing Fibonacci heap, that you will learn about in the second half of the course.

Many thanks to those of you who are giving thumbs up to these videos and subscribing to the channel. Your support is greatly appreciated and it causes Youtube to offer this material to more viewers who might like it.

Course web page:
https://www.cl.cam.ac.uk/teaching/cur...

Course handout:
https://www.cl.cam.ac.uk/teaching/202...

My home page:
http://stajano.com