# What is Heap Data Structure

July 03, 2019

Its a tree based data structure which is a complete binary tree(all nodes have 2 nodes, leaf-child may not have all 2), and satisfies a heap property. But, the amazing thing is that it uses array as its underlying data structure.

The heap is the implementation of the Priority Queue, where top most priority (or lowest priority) element is required to be at the top.

## Heap Property

### 1. Max Heap

In this tree representation, every root node is always greater than both of its child. Note: right child can be lesser than left child.

### 2. Min Heap

As reverse of the max heap. Every root element is always smaller than both of its child elements.

## Operations

Some basic operations on heap are:

• heapify - To maintain either max or min heap property.
• findMax or findMin - To get the top element of heap
• insertElement - To insert a new element to the heap
• extractMax or extractMin - Delete the top element, and return it
• Get heapsize - Get the heap size
• Increment/Decrement - For incrementing or decrementing priority or value of any node

## How array represents the tree (Heap)

As I said earlier, they are based on array, not on any pointers stuff. Consider an array:

``````224,131,23,45,52,287,304,122,460,438
``````

The first element will be the root of tree, 2nd and 3rd are the child of it. 4th and 5th will be child of 2nd node. And so on.

``````            224
/    \
131      23
/   \    /   \
45    52  287   304
/  \    /
122  460  438``````

Note: Above is just tree representation from array. It does not satisfy any max-heap or min-heap property.

## Get Left child

``leftChildIndex = rootIndex * 2 + 1``

## Get Right child

``rightChildIndex = rootIndex * 2 + 2``

## Maintain Heap property - Max Heap

Lets assume we have to build a max heap. We would want every root node to be greater than its child nodes.

### Maintain max heapify property for an index

``````void max_heapify(int[] arr, int index, int heapsize) {
int l = 2 * index + 1;
int r = 2 * index + 2;

int indexOfLargest = index;
if (l < heapsize && arr[l] > arr[index]) {
indexOfLargest = l;
}

if (r < heapsize && arr[r] > arr[indexOfLargest]) {
indexOfLargest = r;
}

if (indexOfLargest != index) {
swap(arr, index, indexOfLargest);
max_heapify(indexOfLargest);
}
}
``````

This operation takes O(log n)

Here for the index passed, we are comparing it with its child elements. If any child is greater than child, it will be swapped. Since, we have put a newer element to its kid. That sub-tree also has to satisfy max-heap property. And, we go in a natural recursive algorithm.

### Build a max heap

``````void buildMaxHeap(int[] arr, int heapsize) {
for (int i=heapsize/2; i>=0; i--) {
max_heapify(arr, i, heapsize);
}
}``````

This operation takes O(n log n) (including time complexity of max_heapify() as well)

## Example

In above example of input, after buildMaxHeap, it will look like:

``````473,445,295,310,404,199,257,25,21,47

473
/    \
445      295
/   \    /   \
310   404 199  257
/  \    /
25  21  47``````

## Use cases of Heap Data Structure

Heap data structure has many usage, and is very useful data structure.

• Used for implementing Priority Queue (Max/Min Priority Queue)
• Maintaining n largest or smallest elements

## Similar Posts

### Maximum Subarray Problem

Problem Statement You are given an array of integers. And, you have find the…

### How to prepare for your next Coding Interview

Here are some tips while preparing for your coding interviews. 1. Do study or…

### Min Priority Queue Implementation with Heap Data structure

Min Priority Queue is a data structure which manage a list of keys(values). And…

### Rotate Array - Leet Code Solution

Problem Statement Given an array, rotate the array to the right by k steps…

### Determine if a string has all unique characters

Problem Implement an algorithm to determine if a string has all the characters…

### Swap Nodes Pairs in Link List - Leet Code Solution

Problem Statement Given a linked list, swap every two adjacent nodes and return…

## Latest Posts

### Python SMTP Email Code - How to Send HTML Email from Python Code with Authentication at SMTP Server

Introduction This post has the complete code to send email through smtp server…

### Python SMTP Email Code - Sender Address Rejected - Not Owned By User

Introduction In a normal email sending code from python, I’m getting following…

### Nodejs with MongoDB - Number of Opened Connections Keep on Increasing with Mongoose Library

Introduction In one of my app, I was using to talk to . I have used some event…

### Django Python - How to Build Docker Image and Run Web-service on Apache with Python 3.9

Introduction So you have a Django project, and want to run it using docker image…

### Python - How to Maintain Quality Build Process Using Pylint and Unittest Coverage With Minimum Threshold Values

Introduction It is very important to introduce few process so that your code and…

### Example Jenkin Groovy Pipeline Script for Building Python Projects with Git Events and Push to Artifactory

Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…