In this tutorial, you will learn the Heap data structure, its operations and basic implementation example with Java

What is Heap Data Structure?

Heap is a tree-based data structure in which all nodes in the tree are in the specific order. There are 2 types of heap, typically:

  • Max Heap: all parent node's values are greater than or equal to children node's values, root node value is the largest.

  • Min Heap: all parent node's values are less than or equal to children node's values, root node value is the smallest.

Basic operations

  • insert aka push, add a new node into the heap
  • remove aka pop, retrieves and removes the min or the max node of the heap
  • examine aka peek, retrieves, but does not remove, the min or the max node of the heap

Internal operations

  • heapify, maintains max or min heap property (all parent node's values should be greater/less than or equal to child node's values)

Implementations

A common implementation of a heap is the binary heap which based on binary tree data structure

You can implement a binary heap with either a static array (capacity restricted) or a dynamic array

Binary Max Heap implementation example with Static Array

Approach

  • Represented by 1-based integer array A[N+1]
  • With a node A[k] (1<=k<=N)
    • Its parent is A[k/2]
    • Left child is A[k*2] (k*2 <= N)
    • Right child is A[k*2+1] (k*2+1 <= N)
  • A[1] is root node, A[0] is Integer.MAX_VALUE

Binary Min Heap implementation example with Static Array

Approach

  • Represented by 1-based integer array A[N+1]
  • With a node A[k] (1<=k<=N)
    • Its parent is A[k/2]
    • Left child is A[k*2] (k*2 <= N)
    • Right child is A[k*2+1] (k*2+1 <= N)
  • A[1] is root node, A[0] is Integer.MIN_VALUE