Heap (structure)

Heaps are a type of data structure that function according to a heap property, which is a specific criterion the heap must fulfil to be valid. Two common types of heaps are min-heaps and max-heaps, which have the property $A[\text{Parent}(i)]\le A[i]$ and $A[\text{Parent}(i)]\ge A[i]$, respectively.

For a max heap, the maximum element is at the root.

The height of a node in a heap is the number of edges on the longest simple downwards path from the node to a leaf. The height of the heap is the height of its root.

A common type of heap is the binary heap, which is visually like and based on a sorted binary tree. This means that its height is $\Theta (\log n)$.

Operations

There are a few operations we want to implement for a max heap:

• Inserting a new element.
• Getting the maximum element.
• Maintaining the max heap property (which runs in $O(\log n)$).

See also

• Heap, a construct in programming languages for dynamically allocated, garbage collected memory