The Heap reference article from the English Wikipedia on 24-Jul-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Heap

This page discusses the heap data structure. For the place where memory is dynamically allocated from, see dynamic memory allocation.

In computer science 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 be nodes of a heap, such that B is a child of A. The heap must then satisfy the 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 the root node. Due to this fact, heaps are used to implement priority queues. The efficiency of heap operations is crucial in several graph algorithms.

The operations commonly performed in a heap are delete-min (removing the root node), decrease-key (updating a key within the heap), and insertion (adding a new key to the heap).

Heaps are used in the sorting algorithm called heapsort.

Variants

• Binary heap
• Binomial heap
• Fibonacci heap
• Soft heap
• 2-3 heap

External links

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