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.

Heap where parent key is greater than or equal to (>=) the child keys are called "MAX-HEAPS"

Heap where parent key is less than or equal to (<=) the child keys are called "MIN-HEAPS"

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.

The heapify can be done in two methodologies:

• up_heapify --> follow a bottom-up approach.

Example

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

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

There is no need to check the left child after this final step.

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

• down_heapify --> follow a top-down approch.

Example

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

The node will swap with the largest one. because, if the node will swap with the smallest, the heap property will still violated

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

There is no need to do more check after the final check because we always swap with the smallest one.

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

Element to be deleted : 6

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

• Step 2, remove the last element

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

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.