Data Structures and Algorithms Using C++

Chapter 11

Priority Queues

The chapter defines priority queues and its abstract data type. It discusses about various implementations of priority queues in detail regarding heaps, insertions and deletions of min and max heaps. This chapter details external sorting using multiway merge and polyphase merge.

11.1 INTRODUCTION

Queues are FIFO structures in which the elements are deleted in the order in which they arrive in the queue. The order of insertion and deletion from a priority queue is determined by the element priority. The elements are removed in the decreasing or increasing order of priority of elements. A priority queue which is a data structure allows at least two operations: insert and delete. The operation insert inserts an element ...