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.


Related Terms

Latest Data Management Terms

Related Reading

Margaret Rouse

Margaret Rouse is an award-winning technical writer and teacher known for her ability to explain complex technical subjects to a non-technical, business audience. Over the past twenty years her explanations have appeared on TechTarget websites and she's been cited as an authority in articles by the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine and Discovery Magazine.Margaret's idea of a fun day is helping IT and business professionals learn to speak each other’s highly specialized languages. If you have a suggestion for a new definition or how to improve a technical explanation, please email Margaret or contact her…