> For the complete documentation index, see [llms.txt](https://www.ctfrecipes.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.ctfrecipes.com/pwn/general-knowledge/operation-of-the-heap/heap-operations.md).

# HEAP operations

HEAP is a data structure that takes the form of a binary tree with two additional constraints:

* Shape property

A binary heap is a **complete binary tree**. It mean that all levels of the tree ( except the last one ) **are fully filled**. If the last level is not complete, the nodes of that level are filled from **left to right**.

* HEAP property 

The key stored in each node is either greter than or equal to (>=) or less than or equal to (<=) the key in node's children.

{% hint style="info" %}
Heap where parent key is greater than or equal to (>=) the child keys are called "**MAX-HEAPS**"&#x20;

Heap where parent key is less than or equal to (<=) the child keys are called "MI&#x4E;**-HEAPS**"&#x20;
{% endhint %}

## Common operations

* **Heapify** --> Process to rearrange the heap in order to maintain heap-property.
* **Insertion** --> Add a new item into the heap
* **Deletion** --> Remove an item from the heap
* **Find-max (or Find-min)** --> find a maximum item of a max-heap, or a minimum item of a min-heap, respectively.
* **Extract Min-Max** → Returning and deleting the maximum or minimum element in max-heap and min-heap respectively.

### Heapify

This process is used to rearrange the elements of the heap in order to maintain the heap property.&#x20;

The heapify can be done in two methodologies:

* **up\_heapify -->** follow a bottom-up approac&#x68;**.**&#x20;

> Example

{% @mermaid/diagram content="graph TD
9 --- 5
9 --- 3
5 --- 1
5 --- 4
3 --- 12" %}

Here the heap property is violated since 12 > 3, so it's needed to swap 12 and 3

{% @mermaid/diagram content="graph TD
9 --- 5
9 --- 12
5 --- 1
5 --- 4
12 --- 3" %}

The heap property is still violated since 12 > 9, so it's needed to swap again.

{% @mermaid/diagram content="graph TD
12 --- 5
12 --- 9
5 --- 1
5 --- 4
9 --- 3" %}

{% hint style="info" %}
**There is no need to check the left child after this final step.**&#x20;

At the start, **the max-heap was valid**, meaning **the root was already greater than its left child**, so replacing the root with an even greater value will maintain the property that each node is greater than its children
{% endhint %}

* **down\_heapify -->** follow a top-down approch.

> Example

{% @mermaid/diagram content="graph TD
1 --- 4
1 --- 6
6 --- 5
4 --- 3
4 --- 2" %}

Here the heap property is violated since 1 < 6 and 1 < 4 , so it's needed to swap

{% hint style="danger" %}
The node will swap with the largest one. because, if the node will swap with the smallest, the heap property will still violated
{% endhint %}

{% @mermaid/diagram content="graph TD
6 --- 4
6 --- 1
1 --- 5
4 --- 3
4 --- 2" %}

The heap property is still violated since 1 < 5, so it's needed to swap again.

{% @mermaid/diagram content="graph TD
6 --- 4
6 --- 5
5 --- 1
4 --- 3
4 --- 2" %}

{% hint style="info" %}
**There is no need to do more check after the final check because we always swap with the smallest one.**&#x20;
{% endhint %}

### Insertion

The insertion in the heap follows the following steps

* Insert the new element at the end of the heap.
* Since the newly inserted element can distort the properties of the Heap. So, a up\_heapify() operation is performed, in order to keep the properties of the heap in a bottom-up approach.

### Deletion

The deletion operations follow the following step:

* Replace the element to be deleted by the last element in the heap.
* Delete the last item from the heap.
* Now, the last element is placed at some position in heap, it may not follow the property of the heap, so a down\_heapify() operation is done in order to maintain heap structure.

> Example

Initially the heap is(It follows max-heap property)

Element to be deleted is 6

{% @mermaid/diagram content="graph TD
6 --- 4
6 --- 5
5 --- 1
4 --- 3
4 --- 2" %}

Element to be deleted : 6

* Step 1, replace the last element with the targeted element to remove

{% @mermaid/diagram content="graph TD
1 --- 4
1 --- 5
5 --- 6
4 --- 3
4 --- 2" %}

* Step 2, remove the last element

{% @mermaid/diagram content="graph TD
1 --- 4
1 --- 5
4 --- 3
4 --- 2" %}

* Realize an heapify down from the replaced element ( here is root )

{% @mermaid/diagram content="graph TD
5 --- 4
4 --- 3
4 --- 2
5 --- 1" %}

### Find-max / Find-min

The maximum element and the minimum element in the max-heap and min-heap is found at the root node of the heap.

### Extract Min-Max

This operation returns and deletes the maximum or minimum element in max-heap and min-heap respectively. The maximum element is found at the root node.