Heap (data structure)
Introduction
A heap is a specialized tree-based data structure that satisfies the heap property. This property dictates that if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. The node at the "top" of the heap (with no parents) is called the root node.
Structure
The heap is one maximally efficient implementation of an abstract data type called a priority queue, and in fact, priority queues are often referred to as "heaps", regardless of how they may be implemented. In a heap, the highest (or lowest) priority element is always stored at the root. However, a heap is not a sorted structure and can be regarded as partially ordered. A heap is a useful data structure when it is necessary to repeatedly remove the object with the highest (or lowest) priority.
A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. The heap data structure, specifically the binary heap, was introduced by J. W. J. Williams in 1964, as a data structure for the heapsort sorting algorithm. Heaps are also crucial in several efficient graph algorithms such as Dijkstra's algorithm.
Heap Operations
Heap data structure provides operations such as insert, delete and extract. The details of these operations are as follows:
Insert
Insert operation is used to insert a new key into the heap. Insertion operation ensures that the heap property is maintained after each insertion.
Delete
Delete operation is used to delete a key from the heap. It requires the key to be deleted to be located first, after which it can be deleted.
Extract
Extract operation is used to extract the root from the heap. This operation also ensures that the heap property is maintained after each extraction.
Heap Variants
There are several variants of the heap data structure. These include:
Binary Heap
A binary heap is a heap where each node has at most two children, which are referred to as the left child and the right child.
Fibonacci Heap
A Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than many other priority queue data structures.
Binomial Heap
A binomial heap is a heap similar to a binary heap but also supports quick merging of two heaps.
Applications
Heap data structure is used in various computing fields. Some of the applications include:
- Implementation of efficient priority queues. - In heap sort algorithm. - In graph algorithms such as Dijkstra’s algorithm, Prim’s algorithm. - Used in many operating systems for process scheduling.