Heap (data structure)

A heap is a specialized tree-based data structure. Its base datatype (used for node keys) must be an ordered set.

Let A and B are nodes of a heap, such that B is a child of A. The heap must then satisfy following condition (heap property):

key(A) ≥ key(B)

This is the only restriction of general heaps. It implies that the greatest (or the smallest, depending on the semantics of a comparison) element is always in root node. Due to this fact, heaps are used to implement priority queues. The efficiency of heap operations is crucial in several graph algorithms.

Common variants include:

• Binary heap
• Binomial heap
• Fibonacci heap
• Soft heap

External links:

• http://www.cs.princeton.edu/~chazelle/pubs.html