Heap (Data Structure)

data-structures algorithms

Definition

Heap

A heap is a specialised tree-based data structure that satisfies the heap property:

• Max-Heap Property: For every node $i$ other than the root, the value of $i$ is at most the value of its parent:$A[\mathrm{parent}(i)]\ge A[i]$. Thus, the largest element in a max-heap is stored at the root.
• Min-Heap Property: For every node $i$ other than the root, the value of $i$ is at least the value of its parent:$A[\mathrm{parent}(i)]\le A[i]$. Thus, the smallest element in a min-heap is stored at the root.

A heap is typically implemented as a complete binary tree, meaning all levels are fully filled except possibly the lowest, which is filled from left to right.

Implementation

Heaps are most efficiently implemented using an array. For a node at index $i$ (using 0-based indexing), its relative positions are determined as follows:

• $\mathrm{parent}(i)=\lfloor \frac{i-1}{2}\rfloor$
• $\mathrm{left}(i)=2i+1$
• $\mathrm{right}(i)=2i+2$

The following diagram illustrates a max-heap and its corresponding representation in an array:

Complexity

The following table outlines the time complexity of common heap operations for a heap containing $n$ elements:

Operation	Complexity	Description
$find-max$	$O(1)$	Access the root element of the heap.
$\mathrm{insert}$	$O(\log n)$	Add an element at the end and “bubble up” to maintain the heap property.
$extract-max$	$O(\log n)$	Replace the root with the last element and “bubble down”.
$build-heap$	$O(n)$	Convert an unordered array into a heap using a bottom-up approach.
$\mathrm{heapify}$	$O(\log n)$	Restore the heap property at a specific node.