Heap
Definition - What does Heap mean?
A heap, in the context of data structure, is a tree-based data structure that satisfies the heap property, where each element is assigned a key value, or weighting. The lower value key always has a parent node with a higher-value key. This is called a max-heap structure, and among all nodes, the root node has the highest key.
Sometimes, a tree-based structure has a reversed structure rule, where an element with a higher value key always has a lower value key as a parent node. This is called a min-heap structure, and among all nodes, the root node has the lowest key.
Techopedia explains Heap
There are no practical restrictions on the number of children each node can have in a heap, even though each node usually has two, at the most. The heap is considered the most efficient implementation of an abstract data type, known as the priority queue. Heap implementation is essential in various graph algorithms (including Dijkstra's algorithm) as well as in the heapsort sorting algorithm.
Heaps have several variances that act as abstract data type priority queue implementations with high efficiency. Many applications, such as graph algorithms, require the implementation of priority queues.
An array is the most common implementation form of heap, where no pointers are needed to link between its elements.
Heaps perform multiple operations, including:
- Find-max: Searches for the highest key node among a group of nodes
- Find-min: Searches for the lowest key node among a group of nodes
- Delete-max: Deletes the highest key node among a group of nodes
- Delete-min: Deletes the lowest key node among a group of nodes
Heaps also include functions that perform merging, insertion and key changes.
