Heap

Last Updated: September 10, 2011

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.

This definition was written in the context of Data Structure