Next:6.1 Binary HeapsUp:DSAPrevious:5.7.3 Multiway Search Trees and B-Trees

6. Priority Queues

A Priority queue is an important abstract data type in Computer Science. Major operations supported by priority queues are INSERT and DELETEMIN. They find extensive use in

implementing schedulers in OS, and distributed systems
representing event lists in discrete event simulation
implementing numerous graph algorithms efficiently
selecting k^th largest or k^th smallest elements in lists (order statistics problems)
sorting applications

Simple ways of implementing a priority queue include:

Linked list - sorted and unsorted
Binary search tree

6.1 Binary Heaps

6.1.1 Implementation of Insert and Deletemin
6.1.2 Creating Heap

6.2 Binomial Queues

6.2.1 Binomial Queue Operations
6.2.2 Binomial Amortized Analysis
6.2.3 Lazy Binomial Queues

6.3 To Probe Further
6.4 Problems
6.5 Programming Assignments

6.5.1 Discrete Event Simulation

eEL,CSA_Dept,IISc,Bangalore