Heap

Why Trust Techopedia

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.

Advertisements

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.

Advertisements

Related Terms

Margaret Rouse
Technology expert
Margaret Rouse
Technology expert

Margaret is an award-winning writer and educator known for her ability to explain complex technical topics to a non-technical business audience. Over the past twenty years, her IT definitions have been published by Que in an encyclopedia of technology terms and cited in articles in the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine, and Discovery Magazine. She joined Techopedia in 2011. Margaret’s idea of ​​a fun day is to help IT and business professionals to learn to speak each other’s highly specialized languages.