Heap
From Freepedia
- This page discusses the heap data structure. For the place from which memory is dynamically allocated, see heap (programming).
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. In this form it implies that the greatest element is always in the root node, and such a heap is sometimes called a max heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min heap.) 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-max or delete-min: removing the root node of a max- or min-heap, respectively,
- decrease-key: updating a key within the heap, and
- insert: adding a new key to the heap.
Heaps are used in the sorting algorithm called heapsort.
