# Heap using Python

**Heap** is a **specialized tree-based data structure** and is used to represent the **priority queue**. In the **heap-sort algorithm**, we have two heaps **min-heap** and **max-heap**.

Let’s take the input as [6,8,9,2,4]

**(i) Min-heap:**In the

**Min-heap**, the “

**Parent node should be less than or equal to the child node”**. Let’s arrange the input as in the tree structure.

In this input,** “8 and 9”** are the **child nodes** of a **parent node “6”** and the parent node 6 **satisfy** the condition.** “2 and 4”** are the **child nodes** of a **parent node “8”** but the parent node 8 **does not satisfy** the condition. So, we have to **swap 8 and 2 **and it is shown in **Img 1**.

Note: The condition is

Parent node should be less than or equal to the child node.

Now, **“2 and 9”** are the **child nodes** of a **parent node “6”** and the parent node 6 **does not satisfy** the condition. So, we have to **swap 6 and 2 **and it is shown in **Img 2**.

Next, **“8 and 4”** are the **child nodes** of a **parent node “6”** and the parent node 6 **does not satisfy** the condition. So, we have to **swap 6 and 4 **and it is shown in **Img 3**.

In **Img 3**, **“4 and 9”** are the **child nodes** of a **parent node “2”** and the parent node 2 **satisfy** the condition & **“8 and 6”** are the **child nodes** of a **parent node “4”** and the parent node 4 **satisfy** the condition. Finally, we formed the **min-heap** structure.

For the

input [6,8,9,2,4], theoutput min-heapis[2,4,9,8,6].

**(ii) Max-heap:**

In the **Max-heap**, the “**Parent node should be greater than or equal to the child node”**. **Fig-Input** represents the same input tree structure.

In **Img 4**, **“8 and 9”** are the **child nodes** of a **parent node “6”** and the parent node 6 **does not** **satisfy** the condition so, we have to **swap 6 and 9 **and it is shown in **Img 5**.

Note: The

Max-heapcondition isParent node should be greater than or equal to the child node.

In **Img 5**, **“8 and 6”** are the **child nodes** of a **parent node “9”** and the parent node 9 **satisfy** the condition & **“2 and 4”** are the **child nodes** of a **parent node “8”** and the parent node 8 **satisfy** the condition. Finally, we formed the **max-heap** structure.

For the

input [6,8,9,2,4], theoutput min-heapis[9,8,6,2,4].

**Implementation of Heap:**

In python, the** heapq** module is used to implement a **heap data structure.** Mainly this module represents the **min-heap **type.

**(i) heapify(input):**

It is used to convert the input list into a **min-heap data structure.**

- Import
**heapq**module. - let’s take the
**input**as**[6,8,9,2,4].** **Heapify**function converts the input into the**min-heap structure.**

Output:

**(ii) heappush(input,element):**

It is used to** insert** the element in the heap and also **maintaining **the **heap structure.**

- Now, the
**heap structure**will be**[2,4,9,8,6].** - Add element “
**5”**in heap structure using**heappush**function**.**

Output:

**(iii) heappop(input):**

It is used to** remove** the smallest element in the heap structure and also **maintaining **the **heap structure.**

- Now, the new
**heap structure**will be**[2,4,5,8,6,9].** - By using
**heappop**, we can**remove**the**smallest element**from the heap.

Output:

**(iv) heappushpop(input,element):**

This function represents the combination of both push and pop functions. In this, the given **element** is** first pushed, **then the** smallest element** is** poped.**

- Let’s take the
**input**as**[6,8,9,3,4].** **Heapify**function converts the input into the**min-heap structure [3,4,9,8,6].****Heappushpop**function adds an element “2” and deletes the smallest element in heap structure “2”.

Output:

**(v) heapreplace(input,element):**

This function also inserts and deletes the element but it is different when compare to heappushpop. In this **heapreplace, the smallest element** is** first popped, **then the **element** is** pushed.**

- Let’s take the same
**input**as**[6,8,9,3,4].** **Heapify**function converts the input into the**min-heap structure [3,4,9,8,6].****Heapreplace**function deletes the smallest element first “2” and adds a new element “2”. Here the poped element is “3”.

Output:

**(vi) nsmallest(k,input):**

It returns the k smallest elements. Ex: **nsmallest(k,input)**

- Let’s take the same
**input**as**[6,8,9,3,4].** **Heapify**function converts the input into the**min-heap structure [3,4,9,8,6].****nsmallest(2, input)**function returns the**two smallest elements [3,4].**

Output:

**(vii) nlargest(k,input):**

It returns the k largest elements. Ex: **nlargest(k,input)**

- Let’s take the same
**input**as**[6,8,9,3,4].** **Heapify**function converts the input into the**min-heap structure [3,4,9,8,6].****nlargest(2, input)**function returns the**two largest elements [9,8].**

Output:

Thank you.