# Heap Data Structure

#### In this tutorial, you will learn what heap data structure is. Also, you will find working examples of heap operations in Python.

Heap data structure is a complete binary tree that satisfies the heap property. It is also called as a binary heap.

A complete binary tree is a special binary tree in which

• every level, except possibly the last, is filled
• all the nodes are as far left as possible

Heap Property is the property of a node in which

• (for max heap) key of each node is always greater than its child node/s and the key of the root node is the largest among all other nodes;
• (for min heap) key of each node is always smaller than the child node/s and the key of the root node is the smallest among all other nodes.

## Heap Operations

Some of the important operations performed on a heap are described below along with their algorithms.

### Heapify

Heapify is the process of creating a heap data structure from a binary tree. It is used to create a Min-Heap or a Max-Heap.

1. Let the input array be
2. Create a complete binary tree from the array
3. Start from the first index of non-leaf node whose index is given by `n/2 - 1`.
4. Set current element `i` as `largest`.
5. The index of left child is given by `2i + 1` and the right child is given by `2i + 2`.
If `leftChild` is greater than `currentElement` (i.e. element at `ith` index), set `leftChildIndex` as largest.
If `rightChild` is greater than element in `largest`, set `rightChildIndex` as `largest`.
6. Swap `largest` with `currentElement`
7. Repeat steps 3-7 until the subtrees are also heapified.

Algorithm

``````Heapify(array, size, i)
set i as largest
leftChild = 2i + 1
rightChild = 2i + 2

if leftChild &gt; array[largest]
set leftChildIndex as largest
if rightChild &gt; array[largest]
set rightChildIndex as largest

swap array[i] and array[largest]``````

To create a Max-Heap:

``````MaxHeap(array, size)
loop from the first index of non-leaf node down to zero
call heapify``````

For Min-Heap, both `leftChild` and `rightChild` must be smaller than the parent for all nodes.

### Insert Element into Heap

Algorithm for insertion in Max Heap

``````If there is no node,
create a newNode.
else (a node is already present)
insert the newNode at the end (last node from left to right.)

heapify the array``````
1. Insert the new element at the end of the tree.
2. Heapify the tree.

For Min Heap, the above algorithm is modified so that `parentNode` is always smaller than `newNode`.

### Delete Element from Heap

Algorithm for deletion in Max Heap

``````If nodeToBeDeleted is the leafNode
remove the node
Else swap nodeToBeDeleted with the lastLeafNode
remove noteToBeDeleted

heapify the array``````
1. Select the element to be deleted.
2. Swap it with the last element.
3. Remove the last element.
4. Heapify the tree.

For Min Heap, above algorithm is modified so that both `childNodes` are greater smaller than `currentNode`.

### Peek (Find max/min)

Peek operation returns the maximum element from Max Heap or minimum element from Min Heap without deleting the node.

For both Max heap and Min Heap

`return rootNode`

### Extract-Max/Min

Extract-Max returns the node with maximum value after removing it from a Max Heap whereas Extract-Min returns the node with minimum after removing it from Min Heap.

## Python Examples

``````/* Max-Heap data structure in Python */

def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2

if l < n and arr[i] < arr[l]:
largest = l

if r < n and arr[largest] < arr[r]:
largest = r

if largest != i:
arr[i],arr[largest] = arr[largest],arr[i]
heapify(arr, n, largest)

def insert(array, newNum):
size = len(array)
if size == 0:
array.append(newNum)
else:
array.append(newNum);
for i in range((size//2)-1, -1, -1):
heapify(array, size, i)

def deleteNode(array, num):
size = len(array)
i = 0
for i in range(0, size):
if num == array[i]:
break

array[i], array[size-1] = array[size-1], array[i]

array.remove(size-1)

for i in range((len(array)//2)-1, -1, -1):
heapify(array, len(array), i)

arr = []

insert(arr, 3)
insert(arr, 4)
insert(arr, 9)
insert(arr, 5)
insert(arr, 2)

print ("Max-Heap array: " + str(arr))

deleteNode(arr, 4)
print("After deleting an element: " + str(arr))

``````

## Heap Data Structure Applications

• Heap is used while implementing a priority queue.
• Dijkstra’s Algorithm
• Heap Sort

# Special 95% discount

## 2000+ Applied Machine Learning & Data Science Recipes

### Portfolio Projects for Aspiring Data Scientists: Tabular Text & Image Data Analytics as well as Time Series Forecasting in Python & R ## Two Machine Learning Fields

There are two sides to machine learning:

• Practical Machine Learning:This is about querying databases, cleaning data, writing scripts to transform data and gluing algorithm and libraries together and writing custom code to squeeze reliable answers from data to satisfy difficult and ill defined questions. It’s the mess of reality.
• Theoretical Machine Learning: This is about math and abstraction and idealized scenarios and limits and beauty and informing what is possible. It is a whole lot neater and cleaner and removed from the mess of reality.

Data Science Resources: Data Science Recipes and Applied Machine Learning Recipes

Introduction to Applied Machine Learning & Data Science for Beginners, Business Analysts, Students, Researchers and Freelancers with Python & R Codes @ Western Australian Center for Applied Machine Learning & Data Science (WACAMLDS) !!!

Latest end-to-end Learn by Coding Recipes in Project-Based Learning:

Applied Statistics with R for Beginners and Business Professionals

Data Science and Machine Learning Projects in Python: Tabular Data Analytics

Data Science and Machine Learning Projects in R: Tabular Data Analytics

Python Machine Learning & Data Science Recipes: Learn by Coding

R Machine Learning & Data Science Recipes: Learn by Coding

Comparing Different Machine Learning Algorithms in Python for Classification (FREE)

`Disclaimer: The information and code presented within this recipe/tutorial is only for educational and coaching purposes for beginners and developers. Anyone can practice and apply the recipe/tutorial presented here, but the reader is taking full responsibility for his/her actions. The author (content curator) of this recipe (code / program) has made every effort to ensure the accuracy of the information was correct at time of publication. The author (content curator) does not assume and hereby disclaims any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from accident, negligence, or any other cause. The information presented here could also be found in public knowledge domains.  `