# 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions