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

• Insert element into queue.
• Extract largest element from queue.

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.

• The Heap data structure
• Implicit Heaps
  • Insert element.- The siftup procedure
  • Delete max element.- The siftdown procedure
• A note on terminology
• Building a heap
• Heapsort