next up previous contents
Next: The Heap data structure Up: Heap implementations and variations Previous: Preface

Heaps - A Priority queue data structure

 

A Heap is a data structure that provides an efficent implementation of priority queue operations. That is, it provides a - first in largest out - queue, according to some ordering relation. In more detail, a priority queue provides at least the following queue operations

This minimal set of primitives are often extended by an AdjustKey operation which adjusts the key of an element already in the queue, and a non desctructive version of ExtractMax which returns the largest element in the queue without removing it from the queue.





Jesper Bojesen
Sat Apr 3 18:07:59 METDST 1999