Encyclopedia > Heap

  Article Content

Heap

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 root node. Due to this fact, heaps are used to implement priority queues. The efficiency of heap operations is crucial in several graph algorithms.

Heaps are used in the sorting algorithm called heapsort.

Common variants include:

External links



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Islandia, New York

... the average family size is 3.49. In the village the population is spread out with 24.7% under the age of 18, 6.9% from 18 to 24, 36.3% from 25 to 44, 25.1% from 45 to 64, ...

 
 
 
This page was created in 25.3 ms