# Introduction to Heap Data Structure

In this article we are going to see **what heap data structure is and what is its ADT operation and the implementation of heap?**

Submitted by Radib Kar, on September 15, 2020

**Prerequisite:** Complete binary tree

## What is Heap?

Heap is a complete binary tree having the below properties:

- Each parent is either greater than its children (max heap) or less than its children (min heap)
- It's a complete binary tree, that means all leaf nodes are either at
(Provided h be the height of the tree) level and if the last level is not full, then the leaf nodes are as far left as possible.*h or h-1*

Below are few examples where the tree is heap or not.

**Example1:**

The above example is a heap and since each parent is smaller than its children, thus it's a min heap.

The above example is a heap and since each parent is greater than its children, thus it's a max heap.

**Example3:**

The above example is not a heap since for the parent 4, it has one child having value greater than it and another having value less than it. So that violates the heap property.

## Type of Heaps

**Min Heap:**

In the min heap, parent is smaller than its children. Example 1**Max heap:**

In the min heap, parent is greater than its children. Example 2

## Heap ADT operations

**Insert (key):**Insert keys to the heap and does heapify to maintain the heap property**GetMin/GetMax:**Returns the root of the heap which is minimum in case of min heap and maximum in case of max heap.**ExtractMin/ExtractMax:**Remove & return the root of the heap which is minimum in case of min heap and maximum in case of max heap.

## Implementation

**1) Using 1D array:**

This is called binary heap where we have an array ** arr **to store the elements. Below is the heap storing information.

- Root is
*arr[0]* - To find parent of a child, parent of child
*arr[i]*would be*arr[(i-1)/2]*where*i>0* - To find left child of a parent, left child of parent
*arr[i]*would be*arr[2*i+1]* - To find left child of a parent, left child of parent
*arr[i]*would be*arr[2*i+2]*

So, if we represent the example1 as binary heap, then it will be:

Array *arr*

**2) Using priority_queue:**

Priority queue is in another implementation for heap where priority is the heap element values.

### Application of Heap

- Data compression, huffman coding
- Shortest path algorithm, Dijkstra's algorithm
- Minimum Spanning tree (Prim's Algorithm)
- Finding kth maximum/ kth minimum

Comments and Discussions!